Paper Info
Title
Clique coloring of binomial random graphs
Abstract
A clique coloring of a graph is a coloring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colors in such a coloring is the clique chromatic number. In this paper, we study the asymptotic behavior 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.
Year
DOI
Venue
2019
10.1002/rsa.20804
RANDOM STRUCTURES & ALGORITHMS
Keywords
DocType
Volume
clique chromatic number,random graphs
Journal
54.0
Issue
ISSN
Citations 
4.0
1042-9832
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Colin McDiarmid11071167.05
Dieter Mitsche214126.08
Pawel Pralat323448.16