The Complexity of Colouring Problems on Dense Graphs

Keith Edwards

doi:10.1016/0304-3975(86)90184-2

The Complexity of Colouring Problems on Dense Graphs

Keith Edwards (Lead / Corresponding author)

Computing

Research output: Contribution to journal › Article › peer-review

79 Citations (Scopus)

Abstract

We consider the problem of deciding whether or not a graph has a vertex k-colouring, restricted to the class of graphs in which each vertex has degree at least an, where a is a fixed positive constant and n is the number of vertices of the graph. We show that there is a deterministic polynomial time algorithm for this problem when a > (k - 3)/(k -2) and that this is best possible. We also consider the corresponding enumeration problems.

Original language	English
Pages (from-to)	337-343
Number of pages	7
Journal	Theoretical Computer Science
Volume	43
DOIs	https://doi.org/10.1016/0304-3975(86)90184-2
Publication status	Published - 1986

Access to Document

10.1016/0304-3975(86)90184-2Licence: Elsevier User Licence

Cite this

@article{13f412a3173247fc8174c3a08d74df7a,

title = "The Complexity of Colouring Problems on Dense Graphs",

abstract = "We consider the problem of deciding whether or not a graph has a vertex k-colouring, restricted to the class of graphs in which each vertex has degree at least an, where a is a fixed positive constant and n is the number of vertices of the graph. We show that there is a deterministic polynomial time algorithm for this problem when a > (k - 3)/(k -2) and that this is best possible. We also consider the corresponding enumeration problems. ",

author = "Keith Edwards",

note = "Copyright: {\textcopyright} 1986, Elsevier Science Publishers B.V. (North-Holland).",

year = "1986",

doi = "10.1016/0304-3975(86)90184-2",

language = "English",

volume = "43",

pages = "337--343",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - The Complexity of Colouring Problems on Dense Graphs

AU - Edwards, Keith

PY - 1986

Y1 - 1986

N2 - We consider the problem of deciding whether or not a graph has a vertex k-colouring, restricted to the class of graphs in which each vertex has degree at least an, where a is a fixed positive constant and n is the number of vertices of the graph. We show that there is a deterministic polynomial time algorithm for this problem when a > (k - 3)/(k -2) and that this is best possible. We also consider the corresponding enumeration problems.

AB - We consider the problem of deciding whether or not a graph has a vertex k-colouring, restricted to the class of graphs in which each vertex has degree at least an, where a is a fixed positive constant and n is the number of vertices of the graph. We show that there is a deterministic polynomial time algorithm for this problem when a > (k - 3)/(k -2) and that this is best possible. We also consider the corresponding enumeration problems.

U2 - 10.1016/0304-3975(86)90184-2

DO - 10.1016/0304-3975(86)90184-2

M3 - Article

SN - 0304-3975

VL - 43

SP - 337

EP - 343

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

The Complexity of Colouring Problems on Dense Graphs

Abstract

Access to Document

Fingerprint

Cite this