Conflict-Free Coloring of Star-Free Graphs on Open Neighborhoods

preprint2020arXivOpen access

Abstract

Given a graph, the conflict-free coloring problem on open neighborhoods (CFON) asks to color the vertices of the graph so that all the vertices have a uniquely colored vertex in its open neighborhood. The smallest number of colors required for such a coloring is called the conflict-free chromatic number and denoted χON(G)χ_{ON}(G). In this note, we study this problem on SkS_k-free graphs where SkS_k is a star on k+1k+1 vertices. When GG is SkS_k-free, we show that χON(G)=O(k⋅log⁡2+εΔ)χ_{ON}(G) = O(k\cdot \log^{2+ε}Δ), for any ε>0ε> 0, where ΔΔ denotes the maximum degree of GG. Further, we show existence of claw-free (S3S_3-free) graphs that require Ω(log⁡Δ)Ω(\log Δ) colors.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.