2024/03/05 by Manuel Fernandez V, Fernandez, Manuel, Lutz Warnke +1
Computer Science · Mathematics · #05C15 #05C80 #60C05 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2403.03013
openalex publication_date 2024/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no maximal clique is monochromatic. In this paper, we determine the order of magnitude of the clique chromatic number of the random graph Gn,p for most edge-probabilities p in the range n-2/5 ≪ p ≪ 1. This resolves open problems and questions of Lichev, Mitsche and Warnke as well as Alon and Krievelevich. One major proof difficulty stems from high-degree vertices, which prevent maximal cliques in their neighborhoods: we deal with these vertices by an intricate union bound argument, that combines the probabilistic method with new degree counting arguments in order to enable Janson's inequality. This way we determine the asymptotics of the clique chromatic number of Gn,p in some ranges, and discover a surprising new phenomenon that contradicts earlier predictions for edge-probabilities p close to n-2/5.