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

Let $G=G(V,E)$ be a graph. A proper coloring of G is a function $f:V\to 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 ${\mathit{\chi }}_{sd}(G)$ . In this paper, we employ entropy compression method to obtain a new upper bound ${\mathit{\chi }}_{sd}(G)\le \lceil \frac{19}{6}{\mathrm{\Delta }}^{\frac{3}{2}}+5\mathrm{\Delta }\rceil$ for general graph G.