The t-improper chromatic number of random graphs

DOI10.1017/S0963548309990216MaRDI QIDQ3557526zbMATH OpenOpenAlexFDO

Authors Ross J. Kang, Colin McDiarmid

Publication date 23 April 2010

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0809.4726

zbMATH Keywords

random graphimproper chromatic number

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Abstract: We consider the $t$-improper chromatic number of the Erd{H o}s-R{'e}nyi random graph $G(n,p)$. The t-improper chromatic number $ch{i}^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 $ch{i}^t(G(n,p))$ over the range of choices for the growth of $t=t(n)$.

Recommendations

• The t-improper chromatic number of random graphs
• The \(t\)-tone chromatic number of random graphs
• On the chromatic number of random graphs
• Improper colouring of (random) unit disk graphs
• Improper colouring of (random) unit disk graphs

Cites work

• Defective coloring revisited
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Generalized Chromatic Numbers of Random Graphs
• Improper colouring of (random) unit disk graphs
• List Improper Colourings of Planar Graphs
• On colouring random graphs
• The chromatic number of random graphs
• The chromatic number of random graphs
• The structure of hereditary properties and colourings of random graphs

Cited in

(16)

• Improper colouring of (random) unit disk graphs
• On generalized choice and coloring numbers
• Improper choosability and property B
• Defective Coloring on Classes of Perfect Graphs
• Largest sparse subgraphs of random graphs
• Dense subgraphs in random graphs
• Bounds and fixed-parameter algorithms for weighted improper coloring
• Parameterized (approximate) defective coloring
• The t-improper chromatic number of random graphs
• The \(t\)-tone chromatic number of random graphs
• Parameterized (approximate) defective coloring
• Coloring random graphs online without creating monochromatic subgraphs
• Entropy of some models of sparse random graphs with vertex-names
• Improper colouring of (random) unit disk graphs
• Largest sparse subgraphs of random graphs
• A precise threshold for quasi-Ramsey numbers

This page was built for publication: The \(t\)-improper chromatic number of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557526)