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

Ejemplares similares

Ejemplares similares