Abstract:
We show complexity results for some generalizations of the graph coloring problem on two classes of perfect graphs, namely clique trees and unit interval graphs. We deal with the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand), and a problem generalizing both of them, the (γ, μ)-coloring problem (lower and upper bounds for the color on each vertex). We characterize the complexity of all those problems on clique trees of different heights, providing polytime algorithms for the cases that are easy. These results have two interesting corollaries: first, one can observe on clique trees of different heights the increasing complexity of the chain k-coloring, μ-coloring, (γ, μ)-coloring, list-coloring. Second, clique trees of height 2 are the first known example of a class of graphs where μ-coloring is polynomial time solvable and precoloring extension is NP-complete, thus being at the same time the first example where μ-coloring is polynomially solvable and (γ, μ)-coloring is NP-complete. Last, we show that the μ-coloring problem on unit interval graphs is NP-complete. These results answer three questions from [Ann. Oper. Res. 169(1) (2009), 3-16]. © 2009 Elsevier B.V. All rights reserved.
Registro:
Documento: |
Artículo
|
Título: | On coloring problems with local constraints |
Autor: | Bonomo, F.; Faenza, Y.; Oriolo, G. |
Filiación: | Università di Roma Tor Vergata, Dipartimento di Ingegneria dell'Impresa, via del Politecnico 1, 00133 Rome, Italy CONICET, Departamento de Computación, FCEyN, Buenos Aires, Argentina
|
Palabras clave: | clique trees; computational complexity; graph coloring problems; unit interval graphs |
Año: | 2009
|
Volumen: | 35
|
Número: | C
|
Página de inicio: | 215
|
Página de fin: | 220
|
DOI: |
http://dx.doi.org/10.1016/j.endm.2009.11.036 |
Título revista: | Electronic Notes in Discrete Mathematics
|
Título revista abreviado: | Electron. Notes Discrete Math.
|
ISSN: | 15710653
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p215_Bonomo |
Referencias:
- Biro, M., Hujter, M., Tuza, Zs., Precoloring extension. I. Interval graphs (1992) Discrete Math., 100 (1-3), pp. 267-279
- Bonomo, F., Cecowski, M., Between coloring and list-coloring: μ-coloring (2005) Electron. Notes Discrete Math., 19, pp. 117-123
- Bonomo, F., Durán, G., Marenco, J., Exploring the complexity boundary between coloring and list-coloring (2009) Ann. Oper. Res., 169 (1), pp. 3-16
- Garey, M., Johnson, D., Miller, G., Papadimitriou, C., The complexity of coloring circular arcs and chords (1980) SIAM J. Alg. Disc. Meth., 1, pp. 216-227
- Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph (1972) SIAM J. Comput., 1 (2), pp. 180-187
- Gusfield, D., Irving, R.W., (1989) The Stable Marriage Problem. Structure and algorithms, , MIT Press, Cambridge, MA
- Hammer, P.L., Maffray, F., Complete separable graphs (1990) Discrete Appl. Math., 27 (1), pp. 85-99
- Hujter, M., Tuza, Zs., Precoloring extension. II. Graph classes related to bipartite graphs (1993) Acta Math. Univ. Comen. 62(1), pp. 1-11
- Hujter, M., Tuza, Zs., Precoloring extension. III. Classes of perfect graphs (1996) Combin. Probab. Comput., 5, pp. 35-56
- Jansen, K., Complexity results for the optimum cost chromatic partition problem (1997), manuscript; Jansen, K., The optimum cost chromatic partition problem (1997) Lect. Notes Comput. Sci., 1203, pp. 25-36
- Jansen, K., Scheffler, P., Generalized coloring for tree-like graphs (1997) Discrete Appl. Math., 75, pp. 135-155
- Roberts, F.S., Indifference graphs (1969) Proof Techniques in Graph Theory, pp. 139-146. , Harary F. (Ed), Academic Press
- Tucker, A., Coloring a family of circular arcs (1975) SIAM J. Appl. Math., 29, pp. 493-502
Citas:
---------- APA ----------
Bonomo, F., Faenza, Y. & Oriolo, G.
(2009)
. On coloring problems with local constraints. Electronic Notes in Discrete Mathematics, 35(C), 215-220.
http://dx.doi.org/10.1016/j.endm.2009.11.036---------- CHICAGO ----------
Bonomo, F., Faenza, Y., Oriolo, G.
"On coloring problems with local constraints"
. Electronic Notes in Discrete Mathematics 35, no. C
(2009) : 215-220.
http://dx.doi.org/10.1016/j.endm.2009.11.036---------- MLA ----------
Bonomo, F., Faenza, Y., Oriolo, G.
"On coloring problems with local constraints"
. Electronic Notes in Discrete Mathematics, vol. 35, no. C, 2009, pp. 215-220.
http://dx.doi.org/10.1016/j.endm.2009.11.036---------- VANCOUVER ----------
Bonomo, F., Faenza, Y., Oriolo, G. On coloring problems with local constraints. Electron. Notes Discrete Math. 2009;35(C):215-220.
http://dx.doi.org/10.1016/j.endm.2009.11.036