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

DOI10.1145/380752.380840zbMATH Open1323.05052OpenAlexW1968496968WikidataQ130979475 ScholiaQ130979475MaRDI QIDQ5176002FDOQ5176002

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

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

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)

Cites Work

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

Cited In (15)

• Title not available (Why is that?)
• 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
• An asymptotically tight bound on the adaptable chromatic number
• Dichotomy for bounded degree \(H\)-colouring
• Graphs with chromatic number close to maximum degree
• (\(\Delta-k\))-critical graphs
• On the Grundy number of a graph
• Asymptotically optimal frugal colouring
• 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)