The t-improper chromatic number of random graphs

DOI10.1017/S0963548309990216zbMATH Open1207.05182arXiv0809.4726OpenAlexW2030362910MaRDI QIDQ3557526FDOQ3557526

Authors: Ross J. Kang, Colin McDiarmid 

Publication date: 23 April 2010

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

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)$.

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

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

zbMATH Keywords

random graphimproper chromatic number

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (16)

• Improper colouring of (random) unit disk graphs
• Improper choosability and property B
• On generalized choice and coloring numbers
• Defective Coloring on Classes of Perfect Graphs
• Largest sparse subgraphs of random graphs
• Dense subgraphs in random graphs
• Parameterized (approximate) defective coloring
• Bounds and fixed-parameter algorithms for weighted improper coloring
• The t-improper chromatic number of random graphs
• Parameterized (approximate) defective coloring
• The \(t\)-tone chromatic number of random graphs
• 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)