B1-EPG graphs are 4-clique colorable

We consider the problem of clique coloring, that is, coloring the vertices of a given graph such that no (maximal) clique of size at least two is monocolored. It is known that interval graphs are 2-clique colorable. In this work we prove that B1-EPG graphs (edge intersection graphs of paths on a gri...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, Flavia, Mazzoleni, María Pía, Stein, Maya
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2017
Materias:
Matemática
clique coloring, edge intersection graphs, paths on grids, polynomial time algorithm
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/79817
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata

Ejemplares similares

Ejemplares similares