The t-Improper Chromatic Number of Random Graphs

DOI10.1017/S0963548309990216zbMath1207.05182arXiv0809.4726OpenAlexW2030362910MaRDI QIDQ3557526

Ross J. Kang, Colin J. H. 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)

Related Items (12)

Unnamed Item ⋮ Improper Choosability and Property B ⋮ A Precise Threshold for Quasi-Ramsey Numbers ⋮ Parameterized (Approximate) Defective Coloring ⋮ On generalized choice and coloring numbers ⋮ Dense subgraphs in random graphs ⋮ ENTROPY OF SOME MODELS OF SPARSE RANDOM GRAPHS WITH VERTEX-NAMES ⋮ Unnamed Item ⋮ Largest sparse subgraphs of random graphs ⋮ Bounds and fixed-parameter algorithms for weighted improper coloring ⋮ Coloring random graphs online without creating monochromatic subgraphs ⋮ Defective Coloring on Classes of Perfect Graphs

Cites Work

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

This page was built for publication: The t-Improper Chromatic Number of Random Graphs