Clique coloring B1-EPG graphs

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 paper we prove that B1-EPG graphs (edge intersection graphs of paths on a gr...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Mazzoleni, M.P., Stein, M.
Formato: JOUR
Materias:
Clique coloring
Edge intersection graphs
Paths on grids
Polynomial time algorithm
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0012365X_v340_n5_p1008_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
Descripción
Sumario: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 paper we prove that B1-EPG graphs (edge intersection graphs of paths on a grid, where each path has at most one bend) are 4-clique colorable. Moreover, given a B1-EPG representation of a graph, we provide a linear time algorithm that constructs a 4-clique coloring of it. © 2017 Elsevier B.V.

Ejemplares similares