Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We deal with some generalizations of the graph coloring problem on classes of perfect graphs. Namely we consider 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 polynomial-time algorithms for the cases that are easy. These results have interesting corollaries. First, one can observe on clique-trees of different heights the increasing complexity of the chain k-coloring, μ-coloring, (γ,μ)-coloring, and 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 Bonomo et al. [F. Bonomo, G. Durn, J. Marenco, Exploring the complexity boundary between coloring and list-coloring, Annals of Operations Research 169 (1) (2009) 3-16]. © 2012 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:Dipartimento di Informatica, Sistemi e Produzione, Università di Roma Tor Vergata, Rome, Italy
IMAS-CONICET, Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
Dipartimento di Matematica Pura e Applicata, Università di Padova, Padua, Italy
Palabras clave:Clique-trees; Computational complexity; Graph coloring; Unit interval graphs
Año:2012
Volumen:312
Número:12-13
Página de inicio:2027
Página de fin:2039
DOI: http://dx.doi.org/10.1016/j.disc.2012.03.019
Título revista:Discrete Mathematics
Título revista abreviado:Discrete Math
ISSN:0012365X
CODEN:DSMHA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0012365X_v312_n12-13_p2027_Bonomo

Referencias:

  • Berge, C., (1960) Les Problmes de Colorations en Théorie des Graphes, 9, pp. 123-160. , Publications de l'Institut de Statistique de l'Université de Paris
  • Biró, M., Hujter, M., Tuza, Zs., Precoloring extension. I. Interval graphs (1992) Discrete Mathematics, 100 (13), pp. 267-279
  • Bonomo, F., Cecowski, M., Between coloring and list-coloring: μ-Coloring (2005) Electronic Notes in Discrete Mathematics, 19, pp. 117-123
  • Bonomo, F., Durn, G., Marenco, J., Exploring the complexity boundary between coloring and list-coloring (2009) Annals of Operations Research, 169 (1), pp. 3-16
  • Brandstdt, A., Bang Le, V., Structure and linear time recognition of 3-leaf powers (2006) Information Processing Letters, 98 (4), pp. 113-138
  • Cacchiani, V., Caprara, A., Toth, P., Solving a real-world train unit assignment problem (2007) ATMOS 2007 - 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, , C. Liebchen, R.K. Ahuja, and J.A. Mesa (Eds.) Dagstuhl, Germany
  • Gavril, F., Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph (1972) SIAM Journal on Computing, 1 (2), pp. 180-187
  • Grtschel, M., Lovsz, L., Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization (1981) Combinatorica, 1, pp. 169-197
  • Hammer, P.L., Maffray, F., Complete separable graphs (1990) Discrete Applied Mathematics, 27 (1), pp. 85-99
  • Hujter, M., Tuza, Zs., Precoloring extension. II. Graph classes related to bipartite graphs (1993) Acta Mathematica Universitatis Comenianae, 62 (1), pp. 1-11
  • Hujter, M., Tuza, Zs., Precoloring extension. III. Classes of perfect graphs (1996) Combinatorics, Probability and Computing, 5, pp. 35-56
  • Jansen, K., (1997) Complexity Results for the Optimum Cost Chromatic Partition Problem, , Manuscript
  • Jansen, K., Scheffler, P., Generalized coloring for tree-like graphs (1997) Discrete Applied Mathematics, 75, pp. 135-155
  • Marx, D., Precoloring extension on unit interval graphs (2006) Discrete Applied Mathematics, 154 (6), pp. 995-1002
  • Nemhauser, G., Wolsey, L., (1988) Integer and Combinatorial Optimization, , Wiley Interscience Series in Discrete Mathematics and Optimization John Wiley & Sons New York
  • Nishimura, N., Radge, N., Thilikos, D.M., On graph powers for leaf-labeled trees (2002) Journal of Algorithms, 42 (1), pp. 69-108
  • Olariu, S., An optimal greedy heuristic to color interval graphs (1991) Information Processing Letters, 37, pp. 21-25
  • Ramalingam, J., Pandu Rangan, C., A unified approach to domination problems on interval graphs (1988) Information Processing Letters, 27, pp. 271-274
  • Roberts, F.S., Indifference graphs (1969) Proof Techniques in Graph Theory, pp. 139-146. , F. Harary, Academic Press
  • Schrijver, A., (1986) Theory of Linear and Integer Programming, , John Wiley
  • Vizing, V., Coloring the vertices of a graph in prescribed colors (1976) Metody Diskretnogo Analiza, 29, pp. 3-10

Citas:

---------- APA ----------
Bonomo, F., Faenza, Y. & Oriolo, G. (2012) . On coloring problems with local constraints. Discrete Mathematics, 312(12-13), 2027-2039.
http://dx.doi.org/10.1016/j.disc.2012.03.019
---------- CHICAGO ----------
Bonomo, F., Faenza, Y., Oriolo, G. "On coloring problems with local constraints" . Discrete Mathematics 312, no. 12-13 (2012) : 2027-2039.
http://dx.doi.org/10.1016/j.disc.2012.03.019
---------- MLA ----------
Bonomo, F., Faenza, Y., Oriolo, G. "On coloring problems with local constraints" . Discrete Mathematics, vol. 312, no. 12-13, 2012, pp. 2027-2039.
http://dx.doi.org/10.1016/j.disc.2012.03.019
---------- VANCOUVER ----------
Bonomo, F., Faenza, Y., Oriolo, G. On coloring problems with local constraints. Discrete Math. 2012;312(12-13):2027-2039.
http://dx.doi.org/10.1016/j.disc.2012.03.019