×

zbMATH — the first resource for mathematics

Precoloring extension. III: Classes of perfect graphs. (English) Zbl 0846.05034
Summary: 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.
For Part I see [Discrete Math. 100, No. 1-3, 267-279 (1992; Zbl 0766.05026)], and for Part II see [Acta Math. Univ. Comen., New Ser. 62, No. 1, 1-11 (1993; Zbl 0821.05026)].

MSC:
05C15 Coloring of graphs and hypergraphs
05C75 Structural characterization of families of graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Jansen, Lecture Notes in Computer Science 657 pp 50– (1993)
[2] König, [Graphs and their applications in the theories of determinants and sets] Matematikai és Természettudományi Értesít? 34 pp 104– (1916)
[3] Hujter, Ada Math. Univ. Comenianae 62 pp 1– (1993)
[4] DOI: 10.1007/BF01584085 · Zbl 0254.90054
[5] Földes, Congr. Numer. 19 pp 311– (1977)
[6] DOI: 10.1137/0214065 · Zbl 0575.68065
[7] DOI: 10.1016/0166-218X(81)90013-5 · Zbl 0463.05057
[8] DOI: 10.1016/0012-365X(92)90646-W · Zbl 0766.05026
[9] DOI: 10.1007/BF02352694 · Zbl 0746.05065
[10] Vizing, Diskret Analiz. 5 pp 9– (1965)
[11] DOI: 10.1137/0202019 · Zbl 0266.05114
[12] DOI: 10.1007/BF01788666 · Zbl 0677.05065
[13] DOI: 10.1017/S0004972700015549 · Zbl 0788.05045
[14] DOI: 10.1016/0166-218X(90)90092-Q · Zbl 0716.05032
[15] Hammer, Rutcor Research Report pp 16– (1989)
[16] Gyárfás, Colloq. Math. Soc. J. Bolyai 4 pp 571– (1970)
[17] Grötschel, Ann. Discrete Math. 21 pp 325– (1984)
[18] DOI: 10.1007/BF02579273 · Zbl 0492.90056
[19] DOI: 10.1002/jgt.3190020209 · Zbl 0411.05060
[20] Golumbic, Algorithmic Graph Theory and Perfect Graphs (1980) · Zbl 0541.05054
[21] DOI: 10.1002/jgt.3190140508 · Zbl 0705.05031
[22] DOI: 10.1016/0095-8956(72)90045-7 · Zbl 0241.05107
[23] DOI: 10.1016/0166-218X(94)90150-3 · Zbl 0807.68055
[24] Kratochvíl, Ada Math. Univ. Comenianae 62 pp 139– (1993)
[25] Hujter, in preparation (1994)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.