The set chromatic number of random graphs

A proper 2-tone k -coloring of a graph is a labeling of the vertices with elements from $${\binom{[k]}{2}}$$ [ k ] 2 such that adjacent vertices receive disjoint labels and vertices distance 2 apart receive distinct labels. The 2-tone chromatic number of a graph G , denoted ₂( ...

For a proper vertex coloring c of a graph G , let c ( G ) denote the maximum, over all induced subgraphs H of G , the difference between the chromatic number ( H ) and the number of colors used by c to color H . We define the chromatic discrepancy of a ...

We prove the theorem from the title: the acyclic edge chromatic number of a random d-regular graph is asymptotically almost surely equal to d + 1. This improves a result of Alon, Sudakov, and Zaks and presents further support for a conjecture that Δ(G) +...