NP-hardness of the recognition of coordinated graphs

A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. In previous w...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Soulignac, F.J., Sueiro, G.
Formato: JOUR
Materias:
Computational complexity
Coordinated graph recognition
NP-complete problems
{gem, C 4, odd hole}-free graphs
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_02545330_v169_n1_p17_Soulignac
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

Ejemplares similares

Ejemplares similares