The t-improper chromatic number of random graphs

Abstract

We consider the $t$-improper chromatic number of the Erd{\H o}s-R{é}nyi random graph $G(n,p)$. The t-improper chromatic number ${\chi }^t(G)$ of $G$ is the smallest number of colours needed in a colouring of the vertices in which each colour class induces a subgraph of maximum degree at most $t$. If $t=0$, then this is the usual notion of proper colouring. When the edge probability $p$ is constant, we provide a detailed description of the asymptotic behaviour of ${\chi }^t(G(n,p))$ over the range of choices for the growth of $t=t(n)$.

12 pages

References in corpus (1)

• The t-stability number of a random graph

Cited by in corpus (9)

• Largest sparse subgraphs of random graphs
• Entropy of Some Models of Sparse Random Graphs With Vertex-Names
• Improper choosability and Property B
• Defective Coloring on Classes of Perfect Graphs
• A precise threshold for quasi-Ramsey numbers
• Coloring random graphs online without creating monochromatic subgraphs
• Bounds and Fixed-Parameter Algorithms for Weighted Improper Coloring (Extended Version)
• The t-stability number of a random graph
• Discrepancy and large dense monochromatic subsets