Navegar

Colección

Datos Estadísticas

Artículo

Bonomo, F.; Durán, G.; Maffray, F.; Marenco, J.; Valencia-Pabon, M. "On the b-coloring of cographs and P 4-sparse graphs" (2009) Graphs and Combinatorics. 25(2):153-167
Estamos trabajando para incorporar este artículo al repositorio
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 coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. 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 b-continuous if it admits a b-coloring with t colors, for every t = χ(G), , χ-b(G). We define a graph G to be b-monotonic if χ b (H 1) ≥χ b (H 2) for every induced subgraph H 1 of G, and every induced subgraph H 2 of H 1. In this work, we prove that P 4-sparse graphs (and, in particular, cographs) are b-continuous and b-monotonic. Besides, we describe a dynamic programming algorithm to compute the b-chromatic number in polynomial time within these graph classes. © 2009 Springer Japan.

Registro:

Documento: Artículo
Título:On the b-coloring of cographs and P 4-sparse graphs
Autor:Bonomo, F.; Durán, G.; Maffray, F.; Marenco, J.; Valencia-Pabon, M.
Filiación:CONICET, Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
CONICET, Departamento de Matemática, Universidad de Buenos Aires, Buenos Aires, Argentina
Departamento de Ingeniería Industrial, FCFM, U. de Chile, Santiago, Chile
C.N.R.S., Laboratoire G-SCOP, Grenoble, France
Instituto de Ciencias, Universidad Nacional de General Sarmiento, Buenos Aires, Argentina
LIPN, Université Paris-Nord, Villetaneuse, France
Palabras clave:B-coloring; B-continuity; B-monotonicity; Cographs; P 4-sparse graphs
Año:2009
Volumen:25
Número:2
Página de inicio:153
Página de fin:167
DOI: http://dx.doi.org/10.1007/s00373-008-0829-1
Título revista:Graphs and Combinatorics
Título revista abreviado:Graphs Comb.
ISSN:09110119
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09110119_v25_n2_p153_Bonomo

Referencias:

  • Blidia, M., Ikhlef-Eschouf, N., Maffray, F., Caractérisation des graphes bγ-parfaits (2007) Actes du 4eme Colloque sur l'Optimisation et les Systèmes d'Information (COSI'2007), pp. 179-190. , Oran, Algeria An English version is given in [2] below
  • Blidia, M., Ikhlef-Eschouf, N., Maffray, F., Characterization of bγ-perfect graphs (2008) Cahiers Leibniz, 171. , http://www.g-scop.inpg.fr/CahiersLeibniz/2008/171/171.html, July
  • Bodlaender, H.L., Achromatic number is NP-complete for cographs and interval graphs (1989) Inf. Proc. Lett., 31, pp. 135-138
  • Corneil, D.G., Lerchs, H., Burlingham L.Stewart, COMPLEMENT REDUCIBLE GRAPHS. (1981) Discrete Applied Mathematics, 3 (3), pp. 163-174. , DOI 10.1016/0166-218X(81)90013-5
  • Corneil, D., Perl, Y., Stewart, L., Cographs: Recognition, applications and algorithms (1984) Cong. Numer., 43, pp. 249-258
  • Corteel, S., Valencia-Pabon, M., Vera, J., On approximating the b-chromatic number (2005) Disc. Appl. Math., 146 (1), pp. 618-622
  • Effantin, B., Kheddouci, H., The b-chromatic number of some power graphs (2003) Disc. Math. & Theor. Comput. Sci., 6 (1), pp. 45-54
  • Faik, T., (2005) La B-continuité des B-colorations : Complexité, Propriétés Structurelles et Algorithmes, , PhD thesis, L.R.I., Université Paris-Sud, Orsay, France
  • Hoang, C.T., Kouider, M., On the b-dominating coloring of graphs (2005) Discrete Applied Mathematics, 152 (1-3), pp. 176-186. , DOI 10.1016/j.dam.2005.04.001, PII S0166218X05000958
  • Hoàng, C.T., Linhares Sales, C., Maffray, F., (2006) On Minimally B-imperfect Graphs, , manuscript
  • Hoàng, C.T., (1985) Perfect Graphs, , PhD thesis, School of Computer Science, McGill University, Montreal
  • Irving, R.W., Manlove, D.F., The b-chromatic number of a graph (1999) Discrete Applied Mathematics, 91 (1-3), pp. 127-141. , PII S0166218X98001462
  • Jamison, B., Olariu, S., Recognizing P 4-sparse graphs in linear time (1992) SIAM J. on Comput., 21, pp. 381-406
  • Jamison, B., Olariu, S., A tree representation for P 4-sparse graphs (1992) Disc. Appl. Math., 35, pp. 115-129
  • Jamison, B., Olariu, S., Linear-time optimization algorithms for p 4-sparse graphs (1995) Disc. Appl. Math., 61, pp. 155-175
  • Jansen, K., Scheffler, P., Woeginger, G.J., Maximum covering with D cliques (1993) Lect. Notes Comput. Sci., 710, pp. 319-328
  • Kára, J., (2004) B-continuity, , Technical Report M 14/04, Technical University Ilmenau, Faculty of Mathematics and Natural Sciences
  • Klein, S., Kouider, M., On b-perfect graphs (2004) Annals of the XII Latin-Ibero-American Congress on Operations Research, , Havanna, Cuba, October
  • Kouider, M., Zaker, M., Bounds for the b-chromatic number of some families of graphs (2006) Dis. Math., 306, pp. 617-623
  • Kratochvíl, J., On the b-chromatic number of a graph (2002) Lect. Notes Comput. Sci., 2573, pp. 310-320
  • Maffray, F., Mechebbek, M., (2007) On B-perfect Chordal Graphs, , manuscript

Citas:

---------- APA ----------
Bonomo, F., Durán, G., Maffray, F., Marenco, J. & Valencia-Pabon, M. (2009) . On the b-coloring of cographs and P 4-sparse graphs. Graphs and Combinatorics, 25(2), 153-167.
http://dx.doi.org/10.1007/s00373-008-0829-1
---------- CHICAGO ----------
Bonomo, F., Durán, G., Maffray, F., Marenco, J., Valencia-Pabon, M. "On the b-coloring of cographs and P 4-sparse graphs" . Graphs and Combinatorics 25, no. 2 (2009) : 153-167.
http://dx.doi.org/10.1007/s00373-008-0829-1
---------- MLA ----------
Bonomo, F., Durán, G., Maffray, F., Marenco, J., Valencia-Pabon, M. "On the b-coloring of cographs and P 4-sparse graphs" . Graphs and Combinatorics, vol. 25, no. 2, 2009, pp. 153-167.
http://dx.doi.org/10.1007/s00373-008-0829-1
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Maffray, F., Marenco, J., Valencia-Pabon, M. On the b-coloring of cographs and P 4-sparse graphs. Graphs Comb. 2009;25(2):153-167.
http://dx.doi.org/10.1007/s00373-008-0829-1