The Complexity of Colouring Problems on Dense Graphs

TY - JOUR

T1 - The Complexity of Colouring Problems on Dense Graphs

AU - Edwards, Keith

N1 - Copyright: © 1986, Elsevier Science Publishers B.V. (North-Holland).

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 -