Brooks-type theorem for r-hued coloring of graphs

DOI10.1016/J.DAM.2023.02.008arXiv2211.01041WikidataQ122526981 ScholiaQ122526981MaRDI QIDQ6415906FDOQ6415906

Authors: Stanislav Jendroľ, Alfréd Onderko 

Publication date: 2 November 2022

Abstract: An $r$-hued coloring of a simple graph $G$ is a proper coloring of its vertices such that every vertex $v$ is adjacent to at least $minr,deg(v)$ differently colored vertices. The minimum number of colors needed for an $r$-hued coloring of a graph $G$, the $r$-hued chromatic number, is denoted by $ch{i}_r(G)$. In this note we show that ${\displaystyle }$chi_r(G) leq (r - 1)(Delta(G) + 1) + 2,${\displaystyle }$ for every simple graph $G$ and every $rgeq2$, which in the case when $r<Delta(G)$ improves the presently known $Delta(G)$-based upper bound on $ch{i}_r(G)$, namely $rDelta(G)+1$. We also discuss the existence of graphs whose $r$-hued chromatic number is close to $(r-1)(Delta+1)+2$ and we prove that there is a bipartite graph of maximum degree $Delta$ whose $r$-hued chromatic number is $(r-1)Delta+1$ for every $rin2,dots,9$ and infinitely many values of $Deltageqr+2$; we believe that $(r-1)Delta(G)+1$ is the best upper bound on the $r$-hued chromatic number of any bipartite graph $G$.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Brooks-type theorem for $r$-hued coloring of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6415906)