Clique coloring of binomial random graphs

DOI10.1002/RSA.20804MaRDI QIDQ5229333zbMATH OpenOpenAlexFDO

Authors D. Mitsche, Paweł Prałat, Colin McDiarmid

Publication date 14 August 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.01782

zbMATH Keywords

clique chromatic numberrandom graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80)

Abstract: A clique colouring of a graph is a colouring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colours in such a colouring is the clique chromatic number. In this paper, we study the asymptotic behaviour of the clique chromatic number of the random graph G(n,p) for a wide range of edge-probabilities p=p(n). We see that the typical clique chromatic number, as a function of the average degree, forms an intriguing step function.

Recommendations

• Clique coloring of dense random graphs
• Tight asymptotics of clique‐chromatic numbers of dense random graphs
• The chromatic number of random graphs
• On the Chromatic Number of Random Graphs
• Tight bounds on the clique chromatic number

Cited in

(8)

• Clique coloring of dense random graphs
• Random perfect graphs
• Tight asymptotics of clique‐chromatic numbers of dense random graphs
• The jump of the clique chromatic number of random graphs
• On the concentration of the chromatic number of random graphs
• Clique colourings of geometric graphs
• The clique chromatic number of sparse random graphs
• Tight bounds on the clique chromatic number

This page was built for publication: Clique coloring of binomial random graphs

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