Artículo
Abstract:
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.
Registro:
| Documento: | Artículo |
| Título: | b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs |
| Autor: | Bonomo, F.; Schaudt, O.; Stein, M.; Valencia-Pabon, M. |
| Filiación: | CONICET and Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina Institut de Mathématiques de Jussieu, CNRS UMR7586, Université Pierre et Marie Curie (Paris 6), Paris, France Centro de Modelamiento Matemático, Universidad de Chile, Santiago, Chile LIPN, CNRS, UMR7030, Université Paris 13, Sorbonne Paris Cité, Villetaneuse, France INRIA Nancy - Grand Est, Nancy, France |
| Palabras clave: | b-Coloring; Co-triangle-free graphs; NP-hardness; Polytime dynamic programming algorithms; Stability number two; Treecographs; Color; Coloring; Dynamic programming; Forestry; Graphic methods; Polynomial approximation; Stability; Trees (mathematics); Dynamic programming algorithm; NP-hardness; Stability number; Treecographs; Triangle-free graphs; Graph theory |
| Año: | 2015 |
| Volumen: | 73 |
| Número: | 2 |
| Página de inicio: | 289 |
| Página de fin: | 305 |
| DOI: | http://dx.doi.org/10.1007/s00453-014-9921-5 |
| Título revista: | Algorithmica |
| Título revista abreviado: | Algorithmica |
| ISSN: | 01784617 |
| CODEN: | ALGOE |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v73_n2_p289_Bonomo |
Referencias:
- Berge, C., Two theorems in graph theory (1957) Proc. Natl. Acad. Sci. USA, 43, pp. 842-844
- Bodlaender, H.L., Achromatic number is NP-complete for cographs and interval graphs (1989) Inf. Process. Lett., 31, pp. 135-138
- Bonomo, F., Durán, G., Maffray, F., Marenco, J., Valencia-Pabon, M., On the b-coloring of cographs and (Formula Presented.)-sparse graphs (2009) Graphs Comb., 25 (2), pp. 153-167
- Dantzig, G.B., Discrete-variable extremum problems (1957) Oper. Res., 5, pp. 266-277
- Edmonds, J., Paths, trees and flowers (1965) Can. J. Math., 17, pp. 449-467
- Faik, T., (2005) La b-continuité des b-colorations: complexité, propriétés structurelles et algorithmes. Ph.D. thesis, L.R.I., Université Paris-Sud, , Orsay, France
- Harary, F., Hedetniemi, S., The achromatic number of a graph (1970) J. Comb. Theory, 8, pp. 154-161
- Havet, F., Linhares-Sales, C., Sampaio, L., b-coloring of tight graphs (2012) Discrete Appl. Math., 160 (18), pp. 2709-2715
- Hoàng, C.T., Kouider, M., On the b-dominating coloring of graphs (2005) Discrete Appl. Math., 152, pp. 176-186
- Hoàng, C.T., Linhares Sales, C., Maffray, F., On minimally b-imperfect graphs (2009) Discrete Appl. Math., 157 (17), pp. 3519-3530
- Irving, R.W., Manlove, D.F., The b-chromatic number of a graph (1999) Discrete Appl. Math., 91, pp. 127-141
- Kára, J., Kratochvíl, J., Voigt, M.: b-Continuity. Technical Report M 14/04, Technical University Ilmenau (2004) Faculty of Mathematics and Natural Sciences
- Kratochvíl, J., Tuza, Z., Voigt, M., On the b-chromatic number of a graph (2002) Lect. Notes Comput. Sci., 2573, pp. 310-320
- Tinhofer, G., Strong tree-cographs are Birkoff graphs (1989) Discrete Appl. Math., 22 (3), pp. 275-288
- Yannakakis, M., Gavril, F., Edge dominating sets in graphs (1980) SIAM J. Appl. Math., 38 (3), pp. 364-372
Citas:
---------- APA ----------
Bonomo, F., Schaudt, O., Stein, M. & Valencia-Pabon, M. (2015) . b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs. Algorithmica, 73(2), 289-305.http://dx.doi.org/10.1007/s00453-014-9921-5
---------- CHICAGO ----------
Bonomo, F., Schaudt, O., Stein, M., Valencia-Pabon, M. "b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs" . Algorithmica 73, no. 2 (2015) : 289-305.http://dx.doi.org/10.1007/s00453-014-9921-5
---------- MLA ----------
Bonomo, F., Schaudt, O., Stein, M., Valencia-Pabon, M. "b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs" . Algorithmica, vol. 73, no. 2, 2015, pp. 289-305.http://dx.doi.org/10.1007/s00453-014-9921-5
---------- VANCOUVER ----------
Bonomo, F., Schaudt, O., Stein, M., Valencia-Pabon, M. b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs. Algorithmica. 2015;73(2):289-305.http://dx.doi.org/10.1007/s00453-014-9921-5
