Colouring graphs whose chromatic number is almost their maximum degree

DOI10.1007/BFB0054323MaRDI QIDQ3839005zbMATH OpenFDO

Authors Michael Molloy, Bruce Reed

Publication date 13 August 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0054323

zbMATH Keywords

algorithmchromatic numbercoloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

As we know, determining if a graph \(G\) with maximum degree \(\Delta\) has a coloring using \(k=\lfloor\Delta-\sqrt \Delta+1\rfloor\) colors is NP-complete provided \(k\geq 3\). In this paper two companion results for graphs whose chromatic number \(\chi(G)\) is close to \(\Delta\) are presented. The first one claims the following: There is a positive \(\varepsilon\) such that for each fixed \(\Delta\) and each \(k\) between \(\Delta+1-\varepsilon\sqrt\Delta\) and \(\Delta+1\), we can determine if \(\chi(G)=k\) in polynomial time. Furthermore, if \(\chi\) is between these two bounds then one can find an optimal coloring in polynomial time. The second is as follows: There is a positive \(\varepsilon\) such that for any \(G\) and each \(k\) between \(\Delta+1-\varepsilon\log\Delta\) and \(\Delta+1\) we can determine if \(\chi(G)=k\) in polynomial time. Furthermore, there is a randomized algorithm to find an optimal coloring with polynomial expected running time on all inputs whose chromatic number lies between these two bounds. In this way the authors point out that the complexity boundary between P and NP-complete coloring problems is (approximately) at \(\Delta-\sqrt\Delta\). For the entire collection see [Zbl 0889.00032].

Recommendations

• Colouring graphs when the number of colours is almost the maximum degree
• The complexity of changing colourings with bounded maximum degree
• Graphs with small chromatic numbers are easy to color
• Colouring graphs when the number of colours is nearly the maximum degree
• The complexity of colouring problems on dense graphs

Cited in

(18)

• The complexity of colouring problems on dense graphs
• Graphs with small chromatic numbers are easy to color
• A strengthening of Brooks' theorem
• (\(\Delta-k\))-critical graphs
• Partitioning a graph into degenerate subgraphs
• Extremal values of the chromatic number for a given degree sequence
• Graphs with chromatic numbers strictly less than their colouring numbers
• Colouring Non-sparse Random Intersection Graphs
• Almost all k-colorable graphs are easy to color
• Graphs with chromatic number close to maximum degree
• On graphs having prescribed clique number, chromatic number, and maximum degree
• Randomly colouring graphs (a combinatorial view)
• Colouring graphs when the number of colours is almost the maximum degree
• Total Chromatic Number of Graphs of Order 2n + l having Maximum Degree 2n − 1
• Colouring graphs when the number of colours is nearly the maximum degree
• To an extremal problem on chromatic numbers of finite graphs
• Algorithmic bounds for the chromatic number†
• Asymptotically optimal frugal colouring

This page was built for publication: Colouring graphs whose chromatic number is almost their maximum degree

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