The set chromatic number of random graphs

2015/02/04 by Andrzej Dudek, Dudek, Andrzej, Dieter Mitsche +3
Computer Science · Mathematics · #05C15 #05C35 #05C80 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1502.01295

openalex publication_date 2015/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we study the set chromatic number of a random graph G(n,p) for a wide range of p=p(n). We show that the set chromatic number, as a function of p, forms an intriguing zigzag shape.

Related

• The oriented chromatic number of random graphs of bounded degree
• The difference between the chromatic and the cochromatic number of a random graph
• The clique chromatic number of sparse random graphs
• Clique colouring of binomial random graphs
• Chromatic number of random graphs: an approach using a recurrence relation