A note on the NP-completeness of the precoloring extension coloring problem in triangle free planar graphs

• Autorzy: Monnot J.
• Języki publikacji: EN

Abstrakty

EN

The precoloring extension coloring problem consists in deciding, given a positive integer k, a graph G = (V,E] and k pairwise disjoint subsets Vo, ..., Vk-1 of V, if there exists a (vertex) coloring S = (So,...,Sk-i) of G such that Vi ⊇ Si, for all i = 0,...,k-1:— 1. In this note, we show that the precoloring extension coloring problem is NP-complete in triangle free planar graphs with maximum degree 4.

Słowa kluczowe

EN

NP-complete problems; precoloring; triangle free planar graphs

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2006
• Tom: Vol. 31, No. 2
• Strony: 169--173
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Monnot J.

• CNRS and LAMSADE, Universite Paris-Dauphine, France,

Bibliografia

• [1] Axenovich M., A note on graph coloring extensions and list colorings, Electronic Journal of Combinatorics, Note, 10, 2003, available at http : //www.combinatorics.org/VolumeiQ/vlOiltoc.html.
• [2] Bodlaender H. L., Jansen K., Woeginger G. J., Scheduling with incompatible jobs, Discrete Appl. Math., 55, 1994, 219-232.
• [3] Chlebikova J., Jansen K., The rf-precoloring problem on ^--degenerate graphs, Proceedings of 2th European Conference on Combinatorics, Graphs, and Applications (EUROCOMB), 2003, 81-85.
• [4] Garey M. R., Johnson D. S., Computers and intractability, a guide to the theory ofNP-completeness, CA, Freeman, 1979.
• [5] Grotzsch H., Ein dreifarbensatz fur dreikreisfreie netze auf der kugel, Wiss. 2, Martin Luther Univ. Halle-Wittenberg, Math. Naturwiss Reihe, 8, 1959, 109-120.
• [6] Hujter M., Tuza Zs., Precoloring extension. II. Graphs classes related to bipartite graphs, ActaMath. Univ. Comeniane, LXII, 1993, 1-11.
• [7] Jansen K., Scheffler P., Generalized Coloring for Tree-like Graphs, Discrete Appl. Math., 75, 1997, 135-155.
• [8] Kratochvil J., Precoloring extension with fixed color bound, Acta Math. Univ. Comen., 62, 1993,139-153.
• [9] Lichtenstein D., Planar formulae and their uses, SIAMJ. Comput., 11, 1982, 329-343.
• [10] Tuza Z., Graph Colorings with Local Restrictions - A Survey, Discussiones Mathematicae, Graph Theory, 17, 1997, 161-228, available at http : //www.sztaki.hu/ tuza/.