Artículo
Bonomo, F.; Durán, G.; Marenco, J. "Exploring the complexity boundary between coloring and list-coloring" (2006) Electronic Notes in Discrete Mathematics. 25(SPEC ISS):41-47
Consulte la política de Acceso Abierto del editor
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: | Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Chile Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina |
| Palabras clave: | coloring; computational complexity; list-coloring |
| Año: | 2006 |
| Volumen: | 25 |
| Número: | SPEC ISS |
| Página de inicio: | 41 |
| Página de fin: | 47 |
| DOI: | http://dx.doi.org/10.1016/j.endm.2006.06.064 |
| 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_v25_nSPECISS_p41_Bonomo |
Referencias:
- Biro, M., Hujter, M., Tuza, Zs., Precoloring extension. I. Interval graphs (1992) Discrete Mathematics, 100 (1-3), pp. 267-279
- Bonomo, F., Cecowski, M., Between coloring and list-coloring: μ-coloring (2005) Electronic Notes in Discrete Mathematics, 19, pp. 117-123
- Colbourn, C.J., The complexity of completing partial Latin squares (1984) Annals of Discrete Mathematics, 8, pp. 25-30
- Grötschel, M., Lovász, L., Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization (1981) Combinatorica, 1, pp. 169-197
- 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
- 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. (2006) . Exploring the complexity boundary between coloring and list-coloring. Electronic Notes in Discrete Mathematics, 25(SPEC ISS), 41-47.http://dx.doi.org/10.1016/j.endm.2006.06.064
---------- CHICAGO ----------
Bonomo, F., Durán, G., Marenco, J. "Exploring the complexity boundary between coloring and list-coloring" . Electronic Notes in Discrete Mathematics 25, no. SPEC ISS (2006) : 41-47.http://dx.doi.org/10.1016/j.endm.2006.06.064
---------- MLA ----------
Bonomo, F., Durán, G., Marenco, J. "Exploring the complexity boundary between coloring and list-coloring" . Electronic Notes in Discrete Mathematics, vol. 25, no. SPEC ISS, 2006, pp. 41-47.http://dx.doi.org/10.1016/j.endm.2006.06.064
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Marenco, J. Exploring the complexity boundary between coloring and list-coloring. Electron. Notes Discrete Math. 2006;25(SPEC ISS):41-47.http://dx.doi.org/10.1016/j.endm.2006.06.064
