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

Ejemplares similares

Ejemplares similares