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: | |
|---|---|
| Otros Autores: | , , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Springer Verlag
2014
|
| Materias: | |
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 06670caa a22007817a 4500 | ||
|---|---|---|---|
| 001 | PAPER-14564 | ||
| 003 | AR-BaUEN | ||
| 005 | 20240816133020.0 | ||
| 008 | 190411s2014 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-84905833472 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Bonomo, F. | |
| 245 | 1 | 0 | |a b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs |
| 260 | |b Springer Verlag |c 2014 | ||
| 270 | 1 | 0 | |m Bonomo, F.; Dep. de Computación, Facultad de Ciencias Exactas Y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina; email: fbonomo@dc.uba.ar |
| 504 | |a Berge, C., Two theorems in graph theory (1957) Proc. Natl. Acad. Sci. U.S.A., 43, pp. 842-844 | ||
| 504 | |a Bodlaender, H.L., Achromatic number is NP-complete for cographs and interval graphs (1989) Inf. Process. Lett., 31, pp. 135-138 | ||
| 504 | |a Bonomo, F., Durán, G., Maffray, F., Marenco, J., Valencia-Pabon, M., On the b-coloring of cographs and P4-sparse graphs (2009) Graphs Comb., 25 (2), pp. 153-167 | ||
| 504 | |a Dantzig, G.B., Discrete-variable extremum problems (1957) Oper. Res., 5, pp. 266-277 | ||
| 504 | |a Edmonds, J., Paths, trees and flowers (1965) Can. J. Math., 17, pp. 449-467 | ||
| 504 | |a 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 | ||
| 504 | |a Harary, F., Hedetniemi, S., The achromatic number of a graph (1970) J. Comb. Theor., 8, pp. 154-161 | ||
| 504 | |a Havet, F., Linhares-Sales, C., Sampaio, L., b-coloring of tight graphs (2012) Discrete Appl. Math., 160 (18), pp. 2709-2715 | ||
| 504 | |a Hoàng, C.T., Kouider, M., On the b-dominating coloring of graphs (2005) Discrete Appl. Math., 152, pp. 176-186 | ||
| 504 | |a Hoàng, C.T., Linhares Sales, C., Maffray, F., On minimally b-imperfect graphs (2009) Discrete Appl. Math., 157 (17), pp. 3519-3530 | ||
| 504 | |a Irving, R.W., Manlove, D.F., The b-chromatic number of a graph (1999) Discrete Appl. Math., 91, pp. 127-141 | ||
| 504 | |a Kára, J., Kratochvíl, J., Voigt, M., (2004) b-continuity, , Technical report M 14/04, Technical University Ilmenau, Faculty of Mathematics and Natural Sciences | ||
| 504 | |a Kratochvíl, J., Tuza, Z., Voigt, M., On the b-Chromatic number of graphs (2002) LNCS, 2573, pp. 310-320. , Kučera, L. (ed.) WG 2002. Springer, Heidelberg | ||
| 504 | |a Tinhofer, G., Strong tree-cographs are Birkoff graphs (1989) Discrete Appl. Math., 22 (3), pp. 275-288 | ||
| 504 | |a Yannakakis, M., Gavril, F., Edge dominating sets in graphs (1980) SIAM J. Appl. Math., 38 (3), pp. 364-372A4 - Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE | ||
| 506 | |2 openaire |e Política editorial | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a Dep. de Computación, Facultad de Ciencias Exactas Y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 593 | |a Institut de Mathématiques de Jussieu, CNRS UMR7586, Université Pierre et Marie Curie (Paris 6), Paris, France | ||
| 593 | |a Centro de Mod. Mat., Universidad de Chile, Santiago, Chile | ||
| 593 | |a Université Paris 13, Sorbonne Paris Cité, CNRS UMR7030, Villetaneuse, France | ||
| 650 | 1 | 7 | |2 spines |a COLOR |
| 650 | 1 | 7 | |2 spines |a COLOR |
| 690 | 1 | 0 | |a COLORING |
| 690 | 1 | 0 | |a COMBINATORIAL OPTIMIZATION |
| 690 | 1 | 0 | |a DYNAMIC PROGRAMMING |
| 690 | 1 | 0 | |a FORESTRY |
| 690 | 1 | 0 | |a POLYNOMIAL APPROXIMATION |
| 690 | 1 | 0 | |a AUGMENTING PATH |
| 690 | 1 | 0 | |a B-CHROMATIC NUMBER |
| 690 | 1 | 0 | |a BIPARTITE GRAPHS |
| 690 | 1 | 0 | |a INDUCED SUBGRAPHS |
| 690 | 1 | 0 | |a POLYNOMIAL-TIME DYNAMIC PROGRAMMING |
| 690 | 1 | 0 | |a PROPER COLORING |
| 690 | 1 | 0 | |a STABILITY NUMBER |
| 690 | 1 | 0 | |a TRIANGLE-FREE GRAPHS |
| 690 | 1 | 0 | |a TREES (MATHEMATICS) |
| 690 | 1 | 0 | |a COLORING |
| 690 | 1 | 0 | |a FORESTRY |
| 690 | 1 | 0 | |a MATHEMATICS |
| 690 | 1 | 0 | |a TREES |
| 700 | 1 | |a Schaudt, O. | |
| 700 | 1 | |a Stein, M. | |
| 700 | 1 | |a Valencia-Pabon, M. | |
| 773 | 0 | |d Springer Verlag, 2014 |g v. 8596 LNCS |h pp. 100-111 |p Lect. Notes Comput. Sci. |n Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |x 03029743 |w (AR-BaUEN)CENRE-983 |z 9783319091730 |t 3rd International Symposium on Combinatorial Optimization, ISCO 2014 | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-84905833472&doi=10.1007%2f978-3-319-09174-7_9&partnerID=40&md5=54992f762164d79acba8f8409891c11d |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/978-3-319-09174-7_9 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_03029743_v8596LNCS_n_p100_Bonomo |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8596LNCS_n_p100_Bonomo |y Registro en la Biblioteca Digital |
| 961 | |a paper_03029743_v8596LNCS_n_p100_Bonomo |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 75517 | ||