Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth

THOMAS EMDEN-WEINERT; STEFAN HOUGARDY; BERND KREUTER

doi:10.1017/S0963548398003678

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

For any integer k, we prove the existence of a uniquely k-colourable graph of girth at least g on at most k12(g+1) vertices whose maximal degree is at most 5k13. From this we deduce that, unless NP=RP, no polynomial time algorithm for k-Colourability on graphs G of girth g(G)[ges ]log[mid ]G[mid ]/13logk and maximum degree Δ(G)[les ]6k13 can exist. We also study several related problems.

Crossref Citations

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Molloy, Michael and Reed, Bruce 2000. k-Colouring when k is close to Δ. Electronic Notes in Discrete Mathematics, Vol. 5, Issue. , p. 235.

Molloy, Michael and Reed, Bruce 2001. Colouring graphs when the number of colours is nearly the maximum degree. p. 462.

Maffray, F. 2003. Recent Advances in Algorithms and Combinatorics. p. 65.

Farzad, Babak Molloy, Michael and Reed, Bruce 2005. (Δ-k)-critical graphs. Journal of Combinatorial Theory, Series B, Vol. 93, Issue. 2, p. 173.

Voll, Ulrich 2005. A novel giant-subgraph phase-transition in sparse random k-partite graphs. Discrete Applied Mathematics, Vol. 153, Issue. 1-3, p. 153.

Zhu, Xuding 2006. Topics in Discrete Mathematics. Vol. 26, Issue. , p. 497.

Bordewich, Magnus Dyer, Martin and Karpinski, Marek 2008. Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Random Structures & Algorithms, Vol. 32, Issue. 3, p. 375.

Siggers, Mark H. 2009. Dichotomy for bounded degree H-colouring. Discrete Applied Mathematics, Vol. 157, Issue. 2, p. 201.

Cao, Yi Culberson, Joseph and Stewart, Lorna 2009. Mathematical Foundations of Computer Science 2009. Vol. 5734, Issue. , p. 199.

Havet, Frédéric and Sampaio, Leonardo 2010. Parameterized and Exact Computation. Vol. 6478, Issue. , p. 170.

Rackham, Tom 2010. The complexity of changing colourings with bounded maximum degree. Information Processing Letters, Vol. 110, Issue. 17, p. 735.

Eschen, Elaine M. Hoàng, Chính T. Spinrad, Jeremy P. and Sritharan, R. 2011. On graphs without a C4 or a diamond. Discrete Applied Mathematics, Vol. 159, Issue. 7, p. 581.

Daneshgar, Amir Rahimi, Alireza and Taati, Siamak 2013. Function simulation, graph grammars and colourings. International Journal of Computer Mathematics, Vol. 90, Issue. 7, p. 1334.

Havet, Frédéric and Sampaio, Leonardo 2013. On the Grundy and b-Chromatic Numbers of a Graph. Algorithmica, Vol. 65, Issue. 4, p. 885.

Nešetřil, Jaroslav 2013. Erdős Centennial. Vol. 25, Issue. , p. 383.

Molloy, Michael and Reed, Bruce 2014. Colouring graphs when the number of colours is almost the maximum degree. Journal of Combinatorial Theory, Series B, Vol. 109, Issue. , p. 134.

Hell, Pavol and Mishra, Aurosish 2014. H-coloring degree-bounded (acyclic) digraphs. Theoretical Computer Science, Vol. 554, Issue. , p. 40.

Cranston, Daniel W. and Rabern, Landon 2015. Brooks' Theorem and Beyond. Journal of Graph Theory, Vol. 80, Issue. 3, p. 199.

Cranston, Daniel W. and Rabern, Landon 2015. Coloring a graph with Δ−1 colors: Conjectures equivalent to the Borodin–Kostochka conjecture that appear weaker. European Journal of Combinatorics, Vol. 44, Issue. , p. 23.

Goedgebeur, Jan and Schaudt, Oliver 2016. Graph-Theoretic Concepts in Computer Science. Vol. 9941, Issue. , p. 109.

Download full list

Article contents

Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth

Abstract

Information

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests