Extremal Results on Conflict-free Coloring
From MaRDI portal
Publication:6509938
arXiv2305.02570MaRDI QIDQ6509938FDOQ6509938
Authors: Sriram Bhyravarapu, Shiwali Gupta, Subrahmanyam Kalyanasundaram, Rogers Mathew 
Abstract: A conflict-free open neighborhood coloring of a graph is an assignment of colors to the vertices such that for every vertex there is a color that appears exactly once in its open neighborhood. For a graph G, the smallest number of colors required for such a coloring is called the conflict-free open neighborhood (CFON) chromatic number and is denoted by chi_{ON}(G). Analogously, we define conflict-free closed neighborhood (CFCN) coloring, and CFCN chromatic number (denoted by chi_{CN}(G)). First studied in 2002, this problem has received considerable attention. We study the CFON and CFCN coloring problems and show the following results. In what follows, Delta denotes the maximum degree of the graph. 1. For a K_{1, k}-free graph G, we show that chi_{ON}(G) = O(k lnDelta). This improves the bound of O(k^2 ln Delta) from [Bhyravarapu, Kalyanasundaram, Mathew, MFCS 2022]. Since chi_{CN}(G) leq 2chi_{ON}(G), our result implies an upper bound on chi_{CN}(G) as well. It is known that there exist separate classes of graphs with chi_{ON}(G) = Omega(lnDelta) and chi_{ON}(G) = Omega(k). 2. Let f(delta) be defined as follows: f(delta) = max {chi_{CN} (G) : G is a graph with minimum degree delta}. It is easy to see that f(delta') geq f(delta) when delta' < delta. It is known [Debski and Przybylo, JGT 2021] that f(c Delta) = Theta(log Delta), for any positive constant c. In this paper, we show that f(cDelta^{1 - epsilon}) = Omega (ln^2 Delta), where c, epsilon are positive constants such that epsilon < 0.75. Together with the known upper bound chi_{CN}(G) = O(ln^2 Delta), this implies that f(cDelta^{1 - epsilon}) = Theta (ln^2 Delta). 3. For a K_{1, k}-free graph G on n vertices, we show that chi_{CN}(G) = O(ln k ln n). This bound is asymptotically tight.
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
This page was built for publication: Extremal Results on Conflict-free Coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6509938)
