Linear Colouring of Binomial Random Graphs

2023/11/14 by Austin Eide, Eide, Austin, Paweł Prałat +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2311.08560

openalex publication_date 2023/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate the linear chromatic number χ_lin(G(n,p)) of the binomial random graph G(n,p) on n vertices in which each edge appears independently with probability p=p(n). For dense random graphs (np → ∞ as n → ∞), we show that asymptotically almost surely χ_lin(G(n,p)) ≥ n (1 - O( (np)^-1/2 ) ) = n(1-o(1)). Understanding the order of the linear chromatic number for subcritical random graphs (np < 1) and critical ones (np=1) is relatively easy. However, supercritical sparse random graphs (np = c for some constant c > 1) remain to be investigated.

Related

• Clique colouring of binomial random graphs
• On-line list colouring of random graphs
• The clique chromatic number of sparse random graphs
• Clique coloring of dense random graphs
• Colouring random subgraphs