b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs

Mostrar todas las versiones(3)

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 (Formula Presented.), is the maximum number t such that G admits a b-coloring with t colors. A graph G is called b-c...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Schaudt, O., Stein, M., Valencia-Pabon, M.
Formato: JOUR
Materias:
b-Coloring
Co-triangle-free graphs
NP-hardness
Polytime dynamic programming algorithms
Stability number two
Treecographs
Color
Coloring
Dynamic programming
Forestry
Graphic methods
Polynomial approximation
Stability
Trees (mathematics)
Dynamic programming algorithm
Stability number
Triangle-free graphs
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_01784617_v73_n2_p289_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_01784617_v73_n2_p289_Bonomo
record_format dspace
spelling todo:paper_01784617_v73_n2_p289_Bonomo2023-10-03T15:08:19Z b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs Bonomo, F. Schaudt, O. Stein, M. Valencia-Pabon, M. b-Coloring Co-triangle-free graphs NP-hardness Polytime dynamic programming algorithms Stability number two Treecographs Color Coloring Dynamic programming Forestry Graphic methods Polynomial approximation Stability Trees (mathematics) Dynamic programming algorithm NP-hardness Stability number Treecographs Triangle-free graphs Graph theory 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 (Formula Presented.), 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 (Formula Presented.), and b-monotonic if (Formula Presented.) for every induced subgraph (Formula Presented.) of G, and every induced subgraph (Formula Presented.) of (Formula Presented.). 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 co-bipartite graph is at least 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 Science+Business Media New York. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_01784617_v73_n2_p289_Bonomo
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
Co-triangle-free graphs
NP-hardness
Polytime dynamic programming algorithms
Stability number two
Treecographs
Color
Coloring
Dynamic programming
Forestry
Graphic methods
Polynomial approximation
Stability
Trees (mathematics)
Dynamic programming algorithm
NP-hardness
Stability number
Treecographs
Triangle-free graphs
Graph theory
spellingShingle b-Coloring
Co-triangle-free graphs
NP-hardness
Polytime dynamic programming algorithms
Stability number two
Treecographs
Color
Coloring
Dynamic programming
Forestry
Graphic methods
Polynomial approximation
Stability
Trees (mathematics)
Dynamic programming algorithm
NP-hardness
Stability number
Treecographs
Triangle-free graphs
Graph theory
Bonomo, F.
Schaudt, O.
Stein, M.
Valencia-Pabon, M.
b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs
topic_facet b-Coloring
Co-triangle-free graphs
NP-hardness
Polytime dynamic programming algorithms
Stability number two
Treecographs
Color
Coloring
Dynamic programming
Forestry
Graphic methods
Polynomial approximation
Stability
Trees (mathematics)
Dynamic programming algorithm
NP-hardness
Stability number
Treecographs
Triangle-free graphs
Graph theory
description 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 (Formula Presented.), 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 (Formula Presented.), and b-monotonic if (Formula Presented.) for every induced subgraph (Formula Presented.) of G, and every induced subgraph (Formula Presented.) of (Formula Presented.). 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 co-bipartite graph is at least 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 Science+Business Media New York.
format JOUR
author Bonomo, F.
Schaudt, O.
Stein, M.
Valencia-Pabon, M.
author_facet Bonomo, F.
Schaudt, O.
Stein, M.
Valencia-Pabon, M.
author_sort Bonomo, F.
title b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs
title_short b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs
title_full b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs
title_fullStr b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs
title_full_unstemmed b-Coloring is NP-hard on Co-bipartite Graphs and Polytime Solvable on Tree-Cographs
title_sort b-coloring is np-hard on co-bipartite graphs and polytime solvable on tree-cographs
url http://hdl.handle.net/20.500.12110/paper_01784617_v73_n2_p289_Bonomo
work_keys_str_mv AT bonomof bcoloringisnphardoncobipartitegraphsandpolytimesolvableontreecographs
AT schaudto bcoloringisnphardoncobipartitegraphsandpolytimesolvableontreecographs
AT steinm bcoloringisnphardoncobipartitegraphsandpolytimesolvableontreecographs
AT valenciapabonm bcoloringisnphardoncobipartitegraphsandpolytimesolvableontreecographs
_version_ 1807314832113795072

Ejemplares similares