b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs

Mostrar todas las versiones(2)

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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Schaudt, O., Stein, M., Valencia-Pabon, M., Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE
Formato: SER
Materias:
Color
Coloring
Combinatorial optimization
Dynamic programming
Forestry
Polynomial approximation
Augmenting path
B-chromatic number
Bipartite graphs
Induced subgraphs
Polynomial-time dynamic programming
Proper coloring
Stability number
Triangle-free graphs
Trees (mathematics)
Mathematics
Trees
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03029743_v8596LNCS_n_p100_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03029743_v8596LNCS_n_p100_Bonomo
record_format dspace
spelling todo:paper_03029743_v8596LNCS_n_p100_Bonomo2023-10-03T15:19:37Z b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs Bonomo, F. Schaudt, O. Stein, M. Valencia-Pabon, M. Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE Color Coloring Combinatorial optimization Dynamic programming Forestry Polynomial approximation Augmenting path B-chromatic number Bipartite graphs Induced subgraphs Polynomial-time dynamic programming Proper coloring Stability number Triangle-free graphs Trees (mathematics) Color Coloring Forestry Mathematics Trees 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 χb(G), 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 t = χ (G),..., χb(G) and b-monotonic if χb (H1) ≥ χb (H2) for every induced subgraph H1 of G, and every induced subgraph H2 of H1. 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 a co-bipartite graph is at most 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 International Publishing. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03029743_v8596LNCS_n_p100_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 Color
Coloring
Combinatorial optimization
Dynamic programming
Forestry
Polynomial approximation
Augmenting path
B-chromatic number
Bipartite graphs
Induced subgraphs
Polynomial-time dynamic programming
Proper coloring
Stability number
Triangle-free graphs
Trees (mathematics)
Color
Coloring
Forestry
Mathematics
Trees
spellingShingle Color
Coloring
Combinatorial optimization
Dynamic programming
Forestry
Polynomial approximation
Augmenting path
B-chromatic number
Bipartite graphs
Induced subgraphs
Polynomial-time dynamic programming
Proper coloring
Stability number
Triangle-free graphs
Trees (mathematics)
Color
Coloring
Forestry
Mathematics
Trees
Bonomo, F.
Schaudt, O.
Stein, M.
Valencia-Pabon, M.
Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE
b-Coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs
topic_facet Color
Coloring
Combinatorial optimization
Dynamic programming
Forestry
Polynomial approximation
Augmenting path
B-chromatic number
Bipartite graphs
Induced subgraphs
Polynomial-time dynamic programming
Proper coloring
Stability number
Triangle-free graphs
Trees (mathematics)
Color
Coloring
Forestry
Mathematics
Trees
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 χb(G), 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 t = χ (G),..., χb(G) and b-monotonic if χb (H1) ≥ χb (H2) for every induced subgraph H1 of G, and every induced subgraph H2 of H1. 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 a co-bipartite graph is at most 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 International Publishing.
format SER
author Bonomo, F.
Schaudt, O.
Stein, M.
Valencia-Pabon, M.
Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE
author_facet Bonomo, F.
Schaudt, O.
Stein, M.
Valencia-Pabon, M.
Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE
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_03029743_v8596LNCS_n_p100_Bonomo
work_keys_str_mv AT bonomof bcoloringisnphardoncobipartitegraphsandpolytimesolvableontreecographs
AT schaudto bcoloringisnphardoncobipartitegraphsandpolytimesolvableontreecographs
AT steinm bcoloringisnphardoncobipartitegraphsandpolytimesolvableontreecographs
AT valenciapabonm bcoloringisnphardoncobipartitegraphsandpolytimesolvableontreecographs
AT associacaoportuguesadeinvestigacaooperacionaldelisboacentrodeinvestigacaooperacionalfaculdadedecienciasdauniversidadefundacaoparaacienciaeatecnologiainstitutonacionaldeestatisticauniversiteparisdauphinelamsade bcoloringisnphardoncobipartitegraphsandpolytimesolvableontreecographs
_version_ 1782026600865333248

Ejemplares similares