Artículo
Bonomo, F.; Palacio, M.C. "Between coloring and list-coloring: μ-coloring" (2011) Ars Combinatoria. 99:383-398
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
A new variation of the coloring problem, μ-coloring, is defined in this paper. A coloring of a graph G = (V,E) is a function f: V → ℕ such that f(v) ≠ f(w) if v is adjacent to w. Given a graph G = (V, E) and a function μ: V → ℕ, G is μ-colorable if it admits a coloring f with f(v) ≤ μ(v) for each v ∈ V. It is proved that μ-coloring lies between coloring and list-coloring, in the sense of generalization of problems and computational complexity. Furthermore, the notion of perfection is extended to μ-coloring, giving rise to a new characterization of cographs. Finally, a polynomial time algorithm to solve μ-coloring for cographs is shown.
Registro:
| Documento: | Artículo |
| Título: | Between coloring and list-coloring: μ-coloring |
| Autor: | Bonomo, F.; Palacio, M.C. |
| Filiación: | Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina |
| Palabras clave: | μ-coloring; Cographs; Coloring; List-coloring; M-perfect graphs; Perfect graphs |
| Año: | 2011 |
| Volumen: | 99 |
| Página de inicio: | 383 |
| Página de fin: | 398 |
| Título revista: | Ars Combinatoria |
| Título revista abreviado: | Ars Comb. |
| ISSN: | 03817032 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v99_n_p383_Bonomo |
Referencias:
- Berge, C., Les problèmes de colorations en théorie des graphes (1960) Publ. Inst. Stat. Univ. Paris, 9, pp. 123-160
- Bonomo, F., Cecowski, M., Between coloring and list-coloring: μ-coloring (2005) Electron. Notes Discrete Math., 19, pp. 117-123
- Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., Vuš kovič, K., Recognizing berge graphs (2005) Combinatorica, 25, pp. 143-187
- Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R., The strong perfect graph theorem (2006) Ann. Math., 164, pp. 51-229
- Chvátal, V., Perfectly ordered graphs (1984) Ann. Discrete Math., 21, pp. 63-65
- Corneil, D., Perl, Y., Stewart, L., Cographs: Recognition, applications and algorithms (1984) Congr. Numer., 43, pp. 249-258
- Duchet, P., (1979) Représentations, Noyaux en Théorie des Graphes et Hypergraphes, , Ph.D. thesis, Université Paris 6, Paris, in french
- Grötschel, M., Lovász, L., Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization (1981) Combinatorica, 1, pp. 169-197
- Hujter, M., Tuza, Zs., Precoloring extension. II. Graph classes related to bipartite graphs, Acta (1993) Math. Univ. Comen., 62 (1), pp. 1-11
- Jansen, K., Schemer, P., Generalized coloring for tree-like graphs (1997) Discrete Appl. Math., 75, pp. 135-155
- Klein, S., Kouider, M., On b-perfect graphs (2004) Ann. XII CLAIO, , Havanna, Cuba, Oct
- Lin, M., (2005), personal communication; Lovász, L., A characterization of perfect graphs (1972) J. Combin. Theory, Ser. B, 13, pp. 95-98
- Tuza, Zs., Graph colorings with local constraints - A survey (1997) Discuss. Math., Graph Theory, 17, pp. 161-228
- Vizing, V., Coloring the vertices of a graph in prescribed colors (1976) Metody Diskret. Analiz., 29, pp. 3-10
- Zhu, X., Circular perfect graphs (2005) J. Graph Theory, 48 (3), pp. 186-209
Citas:
---------- APA ----------
Bonomo, F. & Palacio, M.C. (2011) . Between coloring and list-coloring: μ-coloring. Ars Combinatoria, 99, 383-398.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v99_n_p383_Bonomo [ ]
---------- CHICAGO ----------
Bonomo, F., Palacio, M.C. "Between coloring and list-coloring: μ-coloring" . Ars Combinatoria 99 (2011) : 383-398.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v99_n_p383_Bonomo [ ]
---------- MLA ----------
Bonomo, F., Palacio, M.C. "Between coloring and list-coloring: μ-coloring" . Ars Combinatoria, vol. 99, 2011, pp. 383-398.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v99_n_p383_Bonomo [ ]
---------- VANCOUVER ----------
Bonomo, F., Palacio, M.C. Between coloring and list-coloring: μ-coloring. Ars Comb. 2011;99:383-398.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v99_n_p383_Bonomo [ ]
