On the b-coloring of P4-tidy graphs
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 i...
Guardado en:
Autores principales: | , , |
---|---|
Formato: | Artículo publishedVersion |
Publicado: |
2011
|
Materias: | |
Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n1_p60_Velasquez http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v159_n1_p60_Velasquez_oai |
Aporte de: |
id |
I28-R145-paper_0166218X_v159_n1_p60_Velasquez_oai |
---|---|
record_format |
dspace |
spelling |
I28-R145-paper_0166218X_v159_n1_p60_Velasquez_oai2020-10-19 Velasquez, C.I.B. Bonomo, F. Koch, I. 2011 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. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Koch, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n1_p60_Velasquez info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Discrete Appl Math 2011;159(1):60-68 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 On the b-coloring of P4-tidy graphs info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v159_n1_p60_Velasquez_oai |
institution |
Universidad de Buenos Aires |
institution_str |
I-28 |
repository_str |
R-145 |
collection |
Repositorio Digital de la Universidad de Buenos Aires (UBA) |
topic |
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 |
spellingShingle |
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 Velasquez, C.I.B. Bonomo, F. Koch, I. On the b-coloring of P4-tidy graphs |
topic_facet |
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 |
description |
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. |
format |
Artículo Artículo publishedVersion |
author |
Velasquez, C.I.B. Bonomo, F. Koch, I. |
author_facet |
Velasquez, C.I.B. Bonomo, F. Koch, I. |
author_sort |
Velasquez, C.I.B. |
title |
On the b-coloring of P4-tidy graphs |
title_short |
On the b-coloring of P4-tidy graphs |
title_full |
On the b-coloring of P4-tidy graphs |
title_fullStr |
On the b-coloring of P4-tidy graphs |
title_full_unstemmed |
On the b-coloring of P4-tidy graphs |
title_sort |
on the b-coloring of p4-tidy graphs |
publishDate |
2011 |
url |
http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n1_p60_Velasquez http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v159_n1_p60_Velasquez_oai |
work_keys_str_mv |
AT velasquezcib onthebcoloringofp4tidygraphs AT bonomof onthebcoloringofp4tidygraphs AT kochi onthebcoloringofp4tidygraphs |
_version_ |
1766026672809705472 |