Improved upper bound for the degenerate and star chromatic numbers of graphs

Abstract

Let $G=G(V,E)$ be a graph. A proper coloring of G is a function $f:V\rightarrow N$ such that $f(x)\ne f(y)$ for every edge $xy\in E$. A proper coloring of a graph G such that for every $k\ge 1$, the union of any k color classes induces a $(k-1)$-degenerate subgraph is called a degenerate coloring; a proper coloring of a graph with no two-colored $P_{4}$ is called a star coloring. If a coloring is both degenerate and star, then we call it a degenerate star coloring of graph. The corresponding chromatic number is denoted as $\chi _{sd}(G)$. In this paper, we employ entropy compression method to obtain a new upper bound $\chi _{sd}(G)\le \lceil \frac{19}{6}\Delta ^{\frac{3}{2}}+5\Delta \rceil$ for general graph G.