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

DOI10.1145/380752.380840MaRDI QIDQ5176002zbMATH OpenOpenAlexWikidataFDO

Authors Michael Molloy, Bruce 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

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

Recommendations

• Colouring graphs when the number of colours is almost the maximum degree
• scientific article; zbMATH DE number 1189240
• On the hardness of approximating the chromatic number
• Improved Inapproximability Results for Maximum k-Colorable Subgraph
• The complexity of colouring problems on dense graphs

Cites work

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

Cited in

(15)

• scientific article; zbMATH DE number 1189240 (Why is no real title available?)
• The complexity of changing colourings with bounded maximum degree
• Colouring graphs when the number of colours is almost the maximum degree
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• Path coupling using stopping times and counting independent sets and colorings in hypergraphs
• Randomly colouring graphs (a combinatorial view)
• \(H\)-coloring degree-bounded (acyclic) digraphs
• Dichotomy for bounded degree \(H\)-colouring
• An asymptotically tight bound on the adaptable chromatic number
• Graphs with chromatic number close to maximum degree
• (\(\Delta-k\))-critical graphs
• Asymptotically optimal frugal colouring
• On the Grundy number of a graph
• Brooks' Theorem and Beyond
• On the Grundy and \(b\)-chromatic numbers of a graph

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

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