Abstract:
Many classes of graphs where the vertex coloring problem is polynomially solvable are known, the most prominent being the class of perfect graphs. However, the list-coloring problem is NP-complete for many subclasses of perfect graphs. In this work we explore the complexity boundary between vertex coloring and list-coloring on such subclasses of perfect graphs where the former admits polynomial-time algorithms but the latter is NP-complete. Our goal is to analyze the computational complexity of coloring problems lying "between" (from a computational complexity viewpoint) these two problems: precoloring extension, μ-coloring, and (γ,μ)-coloring. © 2008 Springer Science+Business Media, LLC.
Registro:
Documento: |
Artículo
|
Título: | Exploring the complexity boundary between coloring and list-coloring |
Autor: | Bonomo, F.; Durán, G.; Marenco, J. |
Filiación: | CONICET, Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile CONICET, Departamento de Matemática, Universidad de Buenos Aires, Buenos Aires, Argentina Instituto de Ciencias, Universidad Nacional de General Sarmiento, Buenos Aires, Argentina
|
Palabras clave: | Coloring; Computational complexity; List-coloring |
Año: | 2009
|
Volumen: | 169
|
Número: | 1
|
Página de inicio: | 3
|
Página de fin: | 16
|
DOI: |
http://dx.doi.org/10.1007/s10479-008-0391-5 |
Título revista: | Annals of Operations Research
|
Título revista abreviado: | Ann. Oper. Res.
|
ISSN: | 02545330
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v169_n1_p3_Bonomo |
Referencias:
- Bandelt, H., Mulder, H., Distance-hereditary graphs (1986) Journal of Combinatorial Theory. Series B, 41, pp. 182-208
- Bertossi, A., Dominating sets for split and bipartite graphs (1984) Information Processing Letters, 19, pp. 37-40
- Biro, 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., Durán, G., Marenco, J., Exploring the complexity boundary between coloring and list-coloring (2006) Electronic Notes in Discrete Mathematics, 25, pp. 41-47
- Booth, K., Lueker, G., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms (1976) Journal of Computer Science and Technology, 13, pp. 335-379
- Brandstädt, A., Le, V., Spinrad, J., (1999) Graph Classes: A Survey, , SIAM Philadelphia
- Colbourn, C.J., The complexity of completing partial Latin squares (1984) Annals of Discrete Mathematics, 8, pp. 25-30
- Corneil, D., Perl, Y., Clustering and domination in perfect graphs (1984) Discrete Applied Mathematics, 9, pp. 27-39
- Easton, T., Horton, S., Parker, R., On the complexity of certain completion problems (2000) Congressus Numerantium, 145, pp. 9-31
- Garey, M., Johnson, D., Miller, G., Papadimitriou, C., The complexity of coloring circular arcs and chords (1980) SIAM Journal on Algebraic and Discrete Methods, 1, pp. 216-227
- Golumbic, M., (2004) Algorithmic Graph Theory and Perfect Graphs, , 2 Annals of discrete mathematics 57 North-Holland Amsterdam
- Grötschel, M., Lovász, L., Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization (1981) Combinatorica, 1, pp. 169-197
- Hall, P., On representatives of subsets (1935) Journal of the London Mathematical Society, 10, pp. 26-30
- Hell, P., (2006), Personal communication; Holyer, I., The NP-completeness of edge-coloring (1981) SIAM Journal on Computing, 10, pp. 718-720
- 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., The optimum cost chromatic partition problem (1997) Lecture Notes in Computer Science, 1203, pp. 25-36
- Jansen, K., Scheffler, P., Generalized coloring for tree-like graphs (1997) Discrete Applied Mathematics, 75, pp. 135-155
- König, D., Über graphen und ihre anwendung auf determinantentheorie und mengenlehre (1916) Mathematische Annalen, 77, pp. 453-465
- Kubale, M., Some results concerning the complexity of restricted colorings of graphs (1992) Discrete Applied Mathematics, 36, pp. 35-46
- Marx, D., Precoloring extension on unit interval graphs (2006) Discrete Applied Mathematics, 154, pp. 995-1002
- Nemhauser, G., Wolsey, L., (1988) Integer and Combinatorial Optimization Wiley Interscience Series in Discrete Mathematics and Optimization, , Wiley New York
- Tuza, Zs., Graph colorings with local constraints-a survey (1997) Discussiones Mathematicae. Graph Theory, 17, pp. 161-228
Citas:
---------- APA ----------
Bonomo, F., Durán, G. & Marenco, J.
(2009)
. Exploring the complexity boundary between coloring and list-coloring. Annals of Operations Research, 169(1), 3-16.
http://dx.doi.org/10.1007/s10479-008-0391-5---------- CHICAGO ----------
Bonomo, F., Durán, G., Marenco, J.
"Exploring the complexity boundary between coloring and list-coloring"
. Annals of Operations Research 169, no. 1
(2009) : 3-16.
http://dx.doi.org/10.1007/s10479-008-0391-5---------- MLA ----------
Bonomo, F., Durán, G., Marenco, J.
"Exploring the complexity boundary between coloring and list-coloring"
. Annals of Operations Research, vol. 169, no. 1, 2009, pp. 3-16.
http://dx.doi.org/10.1007/s10479-008-0391-5---------- VANCOUVER ----------
Bonomo, F., Durán, G., Marenco, J. Exploring the complexity boundary between coloring and list-coloring. Ann. Oper. Res. 2009;169(1):3-16.
http://dx.doi.org/10.1007/s10479-008-0391-5