Precoloring Extension III: Classes of Perfect Graphs
M. Hujter, Zs. Tuza
Source record
Source: Crossref
Published: Mar 1, 1996
DOI: 10.1017/s0963548300001826
Open original source ↗Source abstract
We continue the study of the following general problem on the vertex colourings of graphs. Suppose that some vertices of a graph G are assigned to some colours. Can this ‘precolouring’ be extended to a proper colouring of G with at most k colours (for some given k )? 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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.