b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs
A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph G, denoted by χb(G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is called b-continuous if it...
Guardado en:
Autor principal: | |
---|---|
Publicado: |
2014
|
Materias: | |
Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8596LNCS_n_p100_Bonomo http://hdl.handle.net/20.500.12110/paper_03029743_v8596LNCS_n_p100_Bonomo |
Aporte de: |
id |
paper:paper_03029743_v8596LNCS_n_p100_Bonomo |
---|---|
record_format |
dspace |
spelling |
paper:paper_03029743_v8596LNCS_n_p100_Bonomo2023-06-08T15:28:54Z b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs Bonomo, Flavia Color Coloring Combinatorial optimization Dynamic programming Forestry Polynomial approximation Augmenting path B-chromatic number Bipartite graphs Induced subgraphs Polynomial-time dynamic programming Proper coloring Stability number Triangle-free graphs Trees (mathematics) Color Coloring Forestry Mathematics Trees A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph G, denoted by χb(G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is called b-continuous if it admits a b-coloring with t colors, for every t = χ (G),..., χb(G) and b-monotonic if χb (H1) ≥ χb (H2) for every induced subgraph H1 of G, and every induced subgraph H2 of H1. We investigate the b-chromatic number of graphs with stability number two. These are exactly the complements of triangle-free graphs, thus including all complements of bipartite graphs. The main results of this work are the following: 1. We characterize the b-colorings of a graph with stability number two in terms of matchings with no augmenting paths of length one or three. We derive that graphs with stability number two are b-continuous and b-monotonic. 2. We prove that it is NP-complete to decide whether the b-chromatic number of a co-bipartite graph is at most a given threshold. 3. We describe a polynomial time dynamic programming algorithm to compute the b-chromatic number of co-trees. 4. Extending several previous results, we show that there is a polynomial time dynamic programming algorithm for computing the b-chromatic number of tree-cographs. Moreover, we show that tree-cographs are b-continuous and b-monotonic. © 2014 Springer International Publishing. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2014 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8596LNCS_n_p100_Bonomo http://hdl.handle.net/20.500.12110/paper_03029743_v8596LNCS_n_p100_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 |
Color Coloring Combinatorial optimization Dynamic programming Forestry Polynomial approximation Augmenting path B-chromatic number Bipartite graphs Induced subgraphs Polynomial-time dynamic programming Proper coloring Stability number Triangle-free graphs Trees (mathematics) Color Coloring Forestry Mathematics Trees |
spellingShingle |
Color Coloring Combinatorial optimization Dynamic programming Forestry Polynomial approximation Augmenting path B-chromatic number Bipartite graphs Induced subgraphs Polynomial-time dynamic programming Proper coloring Stability number Triangle-free graphs Trees (mathematics) Color Coloring Forestry Mathematics Trees Bonomo, Flavia b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs |
topic_facet |
Color Coloring Combinatorial optimization Dynamic programming Forestry Polynomial approximation Augmenting path B-chromatic number Bipartite graphs Induced subgraphs Polynomial-time dynamic programming Proper coloring Stability number Triangle-free graphs Trees (mathematics) Color Coloring Forestry Mathematics Trees |
description |
A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph G, denoted by χb(G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is called b-continuous if it admits a b-coloring with t colors, for every t = χ (G),..., χb(G) and b-monotonic if χb (H1) ≥ χb (H2) for every induced subgraph H1 of G, and every induced subgraph H2 of H1. We investigate the b-chromatic number of graphs with stability number two. These are exactly the complements of triangle-free graphs, thus including all complements of bipartite graphs. The main results of this work are the following: 1. We characterize the b-colorings of a graph with stability number two in terms of matchings with no augmenting paths of length one or three. We derive that graphs with stability number two are b-continuous and b-monotonic. 2. We prove that it is NP-complete to decide whether the b-chromatic number of a co-bipartite graph is at most a given threshold. 3. We describe a polynomial time dynamic programming algorithm to compute the b-chromatic number of co-trees. 4. Extending several previous results, we show that there is a polynomial time dynamic programming algorithm for computing the b-chromatic number of tree-cographs. Moreover, we show that tree-cographs are b-continuous and b-monotonic. © 2014 Springer International Publishing. |
author |
Bonomo, Flavia |
author_facet |
Bonomo, Flavia |
author_sort |
Bonomo, Flavia |
title |
b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs |
title_short |
b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs |
title_full |
b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs |
title_fullStr |
b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs |
title_full_unstemmed |
b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs |
title_sort |
b-coloring is np-hard on co-bipartite graphs and polytime solvable on tree-cographs |
publishDate |
2014 |
url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8596LNCS_n_p100_Bonomo http://hdl.handle.net/20.500.12110/paper_03029743_v8596LNCS_n_p100_Bonomo |
work_keys_str_mv |
AT bonomoflavia bcoloringisnphardoncobipartitegraphsandpolytimesolvableontreecographs |
_version_ |
1768543897701580800 |