Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro 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), and it is b-monotonic if χb(H1)<χb(H2) for every induced subgraph H1 of G, and every induced subgraph H2 of H1. In this work, we prove that P4-tidy graphs (a generalization of many classes of graphs with few induced P4s) are b-continuous and b-monotonic. Furthermore, we describe a polynomial time algorithm to compute theb-chromatic number for this class of graphs. © 2010 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:On the b-coloring of P4-tidy graphs
Autor:Velasquez, C.I.B.; Bonomo, F.; Koch, I.
Filiación:CONICET, Argentina
Departamento de Computacin, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave:b-coloring; b-continuity; b-monotonicity; P4-tidy graphs; B-chromatic number; b-coloring; b-continuity; Chromatic number; Graph G; Induced subgraphs; Monotonicity; P4-tidy graphs; Polynomial-time algorithms; Color; Coloring; Graphic methods; Polynomial approximation; Graph theory
Año:2011
Volumen:159
Número:1
Página de inicio:60
Página de fin:68
DOI: http://dx.doi.org/10.1016/j.dam.2010.10.002
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0166218X_v159_n1_p60_Velasquez.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v159_n1_p60_Velasquez

Referencias:

  • Babel, L., Olariu, S., On the structure of graphs with few P4s (1998) Discrete Applied Mathematics, 84, pp. 1-13
  • Babel, L., Olariu, S., On the p-connectedness of graphsa survey (1999) Discrete Applied Mathematics, 95 (13), pp. 11-33
  • Bonomo, F., Durn, G., Maffray, F., Marenco, J., Valencia-Pabon, M., On the b-coloring of cographs and P4-sparse graphs (2009) Graphs and Combinatorics, 25 (2), pp. 153-167
  • Campos, V., Linhares Sales, C., Maia, A., Sampaio, R., On b-colorings of graphs with few P4's (2010) Proceedings of the 8th French Combinatorial Conference, , Paris
  • Corneil, D., Lerchs, H., Stewart Burlingham, L., Complement reducible graphs (1981) Discrete Applied Mathematics, 3 (3), pp. 163-174
  • Corneil, D., Perl, Y., Stewart, L., Cographs: Recognition, applications and algorithms (1984) Congressus Numerantium, 43, pp. 249-258
  • Corteel, S., Valencia-Pabon, M., Vera, J., On approximating the b-chromatic number (2005) Discrete Applied Mathematics, 146 (1), pp. 618-622
  • Effantin, B., Kheddouci, H., The b-chromatic number of some power graphs (2003) Discrete Mathematics and Theoretical Computer Science, 6 (1), pp. 45-54
  • Faik, T., (2005) La B-continuité des B-colorations: Complexité, Propriétés Structurelles et Algorithms, , Ph.D. Thesis, LRI Université Paris-Sud, Orsay, France
  • Giakoumakis, V., Roussel, F., Thuillier, H., On P4-tidy graphs (1997) Discrete Mathematics and Theoretical Computer Science, 1, pp. 17-41
  • Hoàng, C.T., (1985) Perfect Graphs, , Ph.D. Thesis, School of Computer Science, McGill University, Montreal
  • Hong, C.T., Kouider, M., On the b-dominating coloring of graphs (2005) Discrete Applied Mathematics, 152, pp. 176-186
  • Hong, C.T., Linhares Sales, C., Maffray, F., On minimally b-imperfect graphs (2009) Discrete Applied Mathematics, 157 (17), pp. 3519-3530
  • Hoàng, C.T., (2010) A Characterization of B-perfect Graphs, , Manuscript
  • Irving, R.W., Manlove, D.F., The b-chromatic number of a graph (1999) Discrete Applied Mathematics, 91, pp. 127-141
  • Jakovac, M., Klavar, S., The b-chromatic number of cubic graphs (2010) Graphs and Combinatorics, 26 (1), pp. 107-118
  • Jamison, B., Olariu, S., A new class of brittle graphs (1989) Studies in Applied Mathematics, 81, pp. 89-92
  • Jamison, B., Olariu, S., P4-reducible graphsa class of uniquely tree representable graphs (1989) Studies in Applied Mathematics, 81, pp. 79-87
  • Jamison, B., Olariu, S., On a unique tree representation for P4-extendible graphs (1991) Discrete Applied Mathematics, 34, pp. 151-164
  • Jamison, B., Olariu, S., P-components and the homogeneous decomposition of graphs (1995) SIAM Journal on Discrete Mathematics, 8, pp. 448-463
  • 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) Discrete Mathematics, 306, pp. 617-623
  • Kratochvl, J., Tuza, Z., Voigt, M., On the b-chromatic number of a graph (2002) Lecture Notes in Computer Science, 2573, pp. 310-320

Citas:

---------- APA ----------
Velasquez, C.I.B., Bonomo, F. & Koch, I. (2011) . On the b-coloring of P4-tidy graphs. Discrete Applied Mathematics, 159(1), 60-68.
http://dx.doi.org/10.1016/j.dam.2010.10.002
---------- CHICAGO ----------
Velasquez, C.I.B., Bonomo, F., Koch, I. "On the b-coloring of P4-tidy graphs" . Discrete Applied Mathematics 159, no. 1 (2011) : 60-68.
http://dx.doi.org/10.1016/j.dam.2010.10.002
---------- MLA ----------
Velasquez, C.I.B., Bonomo, F., Koch, I. "On the b-coloring of P4-tidy graphs" . Discrete Applied Mathematics, vol. 159, no. 1, 2011, pp. 60-68.
http://dx.doi.org/10.1016/j.dam.2010.10.002
---------- VANCOUVER ----------
Velasquez, C.I.B., Bonomo, F., Koch, I. On the b-coloring of P4-tidy graphs. Discrete Appl Math. 2011;159(1):60-68.
http://dx.doi.org/10.1016/j.dam.2010.10.002