zbMATH — the first resource for mathematics

Precoloring extension of co-Meyniel graphs. (English) Zbl 1123.05038
Summary: The precoloring extension problem consists, given a graph \(G\) and a set of nodes to which some colors are already assigned, in finding a coloring of \(G\) with the minimum number of colors which respects the precoloring assignment. This can be reduced to the usual coloring problem on a certain contracted graph. We prove that precoloring extension is polynomial for complements of Meyniel graphs. We answer a question of Hujter and Tuza by showing that “PrExt perfect” graphs are exactly the co-Meyniel graphs, which also generalizes results of M. Hujter and Zs. Tuza [Precoloring extensions I (1992; Zbl 0766.05026), II (1993; Zbl 0821.05026), III (1996; Zbl 0846.05034)] and of A. Hertz [Graphs Comb. 5, 149–157 (1989; Zbl 0677.05065)]. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph belongs to a restricted class of perfect graphs (“co-Artemis” graphs, which are “co-perfectly contractile” graphs), whose perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still depends on the ellipsoid method for coloring perfect graphs.

05C15 Coloring of graphs and hypergraphs
05C17 Perfect graphs
Full Text: DOI
[1] Albertson, M. O.: You can’t paint yourself into a corner. J. Comb. Th. B 73, 189–194 (1998) · Zbl 0910.05026
[2] Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation. Combinatorial optimization problems and their approximability properties. Springer, Berlin (1999) · Zbl 0937.68002
[3] Berge, C.: Graphs. North-Holland, Amsterdam (1985)
[4] Biró, M., Hujter, M., Tuza, Zs.: Precoloring extension. I: Interval graphs. Discrete Math. 100, 267–279 (1992) · Zbl 0766.05026
[5] Bodlaender, H. L., Jansen, K., Woeginger, G.: Scheduling with incompatible jobs. Discrete Appl. Math. 55, 219–232 (1994) · Zbl 0822.68011
[6] Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51–229 (2006) · Zbl 1112.05042
[7] Everett, H., de Figueiredo, C. M. H., Linhares Sales, C., Maffray, F., Porto, O., Reed, B. A.: Even pairs. Perfect Graphs, pp. 67–92. Wiley Interscience, New York (2001) · Zbl 0990.05053
[8] Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, New York (1988) · Zbl 0634.05001
[9] Hertz, A.: Slim graphs. Graphs Combin. 5, 149–157 (1989) · Zbl 0677.05065
[10] Hujter, M., Tuza, Zs. M.: Precoloring extension. II. Graphs classes related to bipartite graphs. Acta Math. Univ. Comen., New Ser. 62, 1–11 (1993) · Zbl 0821.05026
[11] Hujter, M., Tuza, Zs. M.: Precoloring extension. III. Classes of perfect graphs. Comb. Probab. Comput. 5, 35–56 (1996) · Zbl 0846.05034
[12] Jansen. K.: The optimum cost chromatic partition problem. In: Bongiovanni, G. et al. (eds.) Algorithms and Complexity, Proceedings of the CIAC 3, Lecture Notes in Computer Science vol. 1203, pp. 25–36 (1997) · Zbl 1401.68353
[13] Hell, P., Nešetřil, J.: Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, New York (2004)
[14] Maffray, F., Trotignon, N.: A class of perfectly contractile graphs. J. Combin. Th. B 96, 1–19 (2006) · Zbl 1078.05034
[15] Markosyan, S. E., Karapetyan, I. A.: Perfect graphs. Akad. Nauk Armjan. SSR Dokl. 63, 292–296 (1976)
[16] Meyniel, H.: The graphs whose odd cycles have at least two chords. Ann. Disc. Math. 21, 115–119 (1984) · Zbl 0567.05034
[17] Ramírez-Alfonsín, J. L., Reed, B. A.: Perfect Graphs. Wiley Interscience, New York (2001)
[18] Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003) · Zbl 1041.90001
[19] Tuza, Zs.: Graph colorings with local constraints–a survey. Discuss. Math. Graph Theory 17, 161–228 (1997) · Zbl 0923.05027
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.