Artículo

Bonomo, F.; Faenza, Y.; Oriolo, G. "On coloring problems with local constraints" (2009) Electronic Notes in Discrete Mathematics. 35(C):215-220
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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