Colouring graphs when the number of colours is nearly the maximum degree

DOI10.1145/380752.380840zbMath1323.05052OpenAlexW1968496968MaRDI QIDQ5176002

Michael S. O. Molloy, Bruce A. Reed

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380840

zbMATH Keywords

graph colouringprobabilistic methods

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models ⋮ Brooks' Theorem and Beyond ⋮ Path coupling using stopping times and counting independent sets and colorings in hypergraphs ⋮ The complexity of changing colourings with bounded maximum degree ⋮ On the Grundy and \(b\)-chromatic numbers of a graph ⋮ Randomly colouring graphs (a combinatorial view) ⋮ Colouring graphs when the number of colours is almost the maximum degree ⋮ An asymptotically tight bound on the adaptable chromatic number ⋮ Asymptotically optimal frugal colouring ⋮ (\(\Delta-k\))-critical graphs ⋮ On the Grundy Number of a Graph ⋮ Dichotomy for bounded degree \(H\)-colouring ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: Colouring graphs when the number of colours is nearly the maximum degree