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 (Formula Presented.), is the maximum number t such that G admits a b-coloring with t colors. A graph G is called b-c...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_01784617_v73_n2_p289_Bonomo |
| Aporte de: |
| Sumario: | 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 (Formula Presented.), 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 (Formula Presented.), and b-monotonic if (Formula Presented.) for every induced subgraph (Formula Presented.) of G, and every induced subgraph (Formula Presented.) of (Formula Presented.). 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 co-bipartite graph is at least 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 Science+Business Media New York. |
|---|