Upper bounds for the 2-hued chromatic number of graphs in terms of the independence number

Abstract

A 2-hued coloring of a graph $G$ (also known as conditional $(k,2)$-coloring and dynamic coloring) is a coloring such that for every vertex $v\in V(G)$ of degree at least $2$, the neighbors of $v$ receive at least $2$ colors. The smallest integer $k$ such that $G$ has a 2-hued coloring with $k$ colors, is called the {\it 2-hued chromatic number} of $G$ and denoted by ${\chi }_2(G)$. In this paper, we will show that if $G$ is a regular graph, then ${\chi }_2(G)-\chi (G)\le 2{\log }_2(\alpha (G))+\mathcal{O}(1)$ and if $G$ is a graph and $\delta (G)\ge 2$, then ${\chi }_2(G)-\chi (G)\le 1+\lceil \sqrt[\delta -1]{4{\Delta }^2}\rceil (1+{\log }_{\frac{2\Delta (G)}{2\Delta (G)-\delta (G)}}(\alpha (G)))$ and in general case if $G$ is a graph, then ${\chi }_2(G)-\chi (G)\le 2+\min \{{\alpha }^{\prime }(G),\frac{\alpha (G)+\omega (G)}{2}\}$.

arXiv commentDynamic chromatic number; conditional (k, 2)-coloring; 2-hued chromatic number; 2-hued coloring; Independence number; Probabilistic method

Cited by in corpus (3)

• $(2/2/3)$-SAT problem and its applications in dominating set problems
• A counterexample to Montgomery's conjecture on dynamic colourings of regular graphs
• r-Dynamic Chromatic Number of Graphs