On the b-coloring of P4-tidy graphs

Mostrar todas las versiones(3)

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

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Velasquez, C.I.B., Bonomo, F., Koch, I.
Formato:	JOUR
Materias:	b-coloring b-continuity b-monotonicity P4-tidy graphs B-chromatic number Chromatic number Graph G Induced subgraphs Monotonicity Polynomial-time algorithms Color Coloring Graphic methods Polynomial approximation Graph theory
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n1_p60_Velasquez
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_0166218X_v159_n1_p60_Velasquez
record_format	dspace
spelling	todo:paper_0166218X_v159_n1_p60_Velasquez2023-10-03T15:03:38Z On the b-coloring of P4-tidy graphs Velasquez, C.I.B. Bonomo, F. Koch, I. 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 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n1_p60_Velasquez
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (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	JOUR
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
url	http://hdl.handle.net/20.500.12110/paper_0166218X_v159_n1_p60_Velasquez
work_keys_str_mv	AT velasquezcib onthebcoloringofp4tidygraphs AT bonomof onthebcoloringofp4tidygraphs AT kochi onthebcoloringofp4tidygraphs
_version_	1807318886594379776

On the b-coloring of P4-tidy graphs

Ejemplares similares