Back to Search
Start Over
Clique coloring of binomial random graphs
- Source :
- Random Structures and Algorithms, Random Structures and Algorithms, Wiley, 2018, ⟨10.1002/rsa.20804⟩
- Publication Year :
- 2018
- Publisher :
- Wiley, 2018.
-
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.<br />25 pages
- Subjects :
- Random graph
Clique
Thesaurus (information retrieval)
Binomial (polynomial)
Applied Mathematics
General Mathematics
Probability (math.PR)
010102 general mathematics
0102 computer and information sciences
01 natural sciences
Computer Graphics and Computer-Aided Design
[MATH.MATH-PR]Mathematics [math]/Probability [math.PR]
Combinatorics
Computer Science::Discrete Mathematics
010201 computation theory & mathematics
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
FOS: Mathematics
Mathematics - Combinatorics
Combinatorics (math.CO)
0101 mathematics
Mathematics - Probability
Software
Mathematics
Subjects
Details
- ISSN :
- 10982418 and 10429832
- Volume :
- 54
- Database :
- OpenAIRE
- Journal :
- Random Structures & Algorithms
- Accession number :
- edsair.doi.dedup.....e2d73621baeff670ba9516730f04250e