Navegar

Colección

Datos Estadísticas

Artículo

Bonomo, F.; Schaudt, O.; Stein, M.; Valencia-Pabon, M.; 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 "b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs" (2014) 3rd International Symposium on Combinatorial Optimization, ISCO 2014. 8596 LNCS:100-111
El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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 χ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.

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.; 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
Ciudad:Lisbon
Filiación:Dep. de Computación, Facultad de Ciencias Exactas Y Naturales, 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 Mod. Mat., Universidad de Chile, Santiago, Chile
Université Paris 13, Sorbonne Paris Cité, CNRS UMR7030, Villetaneuse, France
Palabras clave: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ño:2014
Volumen:8596 LNCS
Página de inicio:100
Página de fin:111
DOI: http://dx.doi.org/10.1007/978-3-319-09174-7_9
Título revista:3rd International Symposium on Combinatorial Optimization, ISCO 2014
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8596LNCS_n_p100_Bonomo

Referencias:

  • Berge, C., Two theorems in graph theory (1957) Proc. Natl. Acad. Sci. U.S.A., 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 P4-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. Theor., 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., (2004) b-continuity, , Technical report M 14/04, Technical University Ilmenau, Faculty of Mathematics and Natural Sciences
  • 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
  • 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-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

Citas:

---------- APA ----------
Bonomo, F., Schaudt, O., Stein, M., Valencia-Pabon, M. & 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 (2014) . b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs. 3rd International Symposium on Combinatorial Optimization, ISCO 2014, 8596 LNCS, 100-111.
http://dx.doi.org/10.1007/978-3-319-09174-7_9
---------- CHICAGO ----------
Bonomo, F., Schaudt, O., Stein, M., Valencia-Pabon, M., 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 "b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs" . 3rd International Symposium on Combinatorial Optimization, ISCO 2014 8596 LNCS (2014) : 100-111.
http://dx.doi.org/10.1007/978-3-319-09174-7_9
---------- MLA ----------
Bonomo, F., Schaudt, O., Stein, M., Valencia-Pabon, M., 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 "b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs" . 3rd International Symposium on Combinatorial Optimization, ISCO 2014, vol. 8596 LNCS, 2014, pp. 100-111.
http://dx.doi.org/10.1007/978-3-319-09174-7_9
---------- VANCOUVER ----------
Bonomo, F., Schaudt, O., Stein, M., Valencia-Pabon, M., 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 b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs. Lect. Notes Comput. Sci. 2014;8596 LNCS:100-111.
http://dx.doi.org/10.1007/978-3-319-09174-7_9