Between coloring and list-coloring: μ-coloring
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...
Guardado en:
| Autor principal: | |
|---|---|
| Publicado: |
2011
|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v99_n_p383_Bonomo http://hdl.handle.net/20.500.12110/paper_03817032_v99_n_p383_Bonomo |
| Aporte de: |
| id |
paper:paper_03817032_v99_n_p383_Bonomo |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_03817032_v99_n_p383_Bonomo2023-06-08T15:40:50Z Between coloring and list-coloring: μ-coloring Bonomo, Flavia μ-coloring Cographs Coloring List-coloring M-perfect graphs Perfect graphs 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. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v99_n_p383_Bonomo http://hdl.handle.net/20.500.12110/paper_03817032_v99_n_p383_Bonomo |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
μ-coloring Cographs Coloring List-coloring M-perfect graphs Perfect graphs |
| spellingShingle |
μ-coloring Cographs Coloring List-coloring M-perfect graphs Perfect graphs Bonomo, Flavia Between coloring and list-coloring: μ-coloring |
| topic_facet |
μ-coloring Cographs Coloring List-coloring M-perfect graphs Perfect graphs |
| description |
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. |
| author |
Bonomo, Flavia |
| author_facet |
Bonomo, Flavia |
| author_sort |
Bonomo, Flavia |
| title |
Between coloring and list-coloring: μ-coloring |
| title_short |
Between coloring and list-coloring: μ-coloring |
| title_full |
Between coloring and list-coloring: μ-coloring |
| title_fullStr |
Between coloring and list-coloring: μ-coloring |
| title_full_unstemmed |
Between coloring and list-coloring: μ-coloring |
| title_sort |
between coloring and list-coloring: μ-coloring |
| publishDate |
2011 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v99_n_p383_Bonomo http://hdl.handle.net/20.500.12110/paper_03817032_v99_n_p383_Bonomo |
| work_keys_str_mv |
AT bonomoflavia betweencoloringandlistcoloringmcoloring |
| _version_ |
1768546496035160064 |