Precoloring Extension III: Classes of Perfect Graphs

1 March 1996

journal article
research article
Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing

Vol. 5 (1) , 35-56
https://doi.org/10.1017/s0963548300001826

Abstract

We continue the study of the following general problem on the vertex colourings of graphs. Suppose that some vertices of a graphGare assigned to some colours. Can this ‘precolouring’ be extended to a proper colouring ofGwith at mostkcolours (for some givenk)? Here we investigate the complexity status of precolouring extendibility on some classes of perfect graphs, giving good characterizations (necessary and sufficient conditions) that lead to algorithms with linear or polynomial running time. It is also shown how a larger subclass of perfect graphs can be derived from graphs containing no induced path on four vertices.

Keywords

This publication has 16 references indexed in Scilit:

Two graph-colouring games
Bulletin of the Australian Mathematical Society, 1993
Generalized coloring for tree-like graphs
Published by Springer Nature ,1993
Precoloring extension. I. Interval graphs
Discrete Mathematics, 1992
Dominating cliques in P5-free graphs
Periodica Mathematica Hungarica, 1990
Difference graphs
Discrete Applied Mathematics, 1990
Slim graphs
Graphs and Combinatorics, 1989
A Linear Recognition Algorithm for Cographs
SIAM Journal on Computing, 1985
Complement reducible graphs
Discrete Applied Mathematics, 1981
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
SIAM Journal on Computing, 1973
Blocking and anti-blocking pairs of polyhedra
Mathematical Programming, 1971