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...
| Autores principales: | , , |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Inglés |
| Publicado: |
2017
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/79817 |
| Aporte de: |
| id |
I19-R120-10915-79817 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Inglés |
| topic |
Matemática clique coloring, edge intersection graphs, paths on grids, polynomial time algorithm |
| spellingShingle |
Matemática clique coloring, edge intersection graphs, paths on grids, polynomial time algorithm Bonomo, Flavia Mazzoleni, María Pía Stein, Maya B1-EPG graphs are 4-clique colorable |
| topic_facet |
Matemática clique coloring, edge intersection graphs, paths on grids, polynomial time algorithm |
| description |
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 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. |
| format |
Objeto de conferencia Objeto de conferencia |
| author |
Bonomo, Flavia Mazzoleni, María Pía Stein, Maya |
| author_facet |
Bonomo, Flavia Mazzoleni, María Pía Stein, Maya |
| author_sort |
Bonomo, Flavia |
| title |
B1-EPG graphs are 4-clique colorable |
| title_short |
B1-EPG graphs are 4-clique colorable |
| title_full |
B1-EPG graphs are 4-clique colorable |
| title_fullStr |
B1-EPG graphs are 4-clique colorable |
| title_full_unstemmed |
B1-EPG graphs are 4-clique colorable |
| title_sort |
b1-epg graphs are 4-clique colorable |
| publishDate |
2017 |
| url |
http://sedici.unlp.edu.ar/handle/10915/79817 |
| work_keys_str_mv |
AT bonomoflavia b1epggraphsare4cliquecolorable AT mazzolenimariapia b1epggraphsare4cliquecolorable AT steinmaya b1epggraphsare4cliquecolorable |
| bdutipo_str |
Repositorios |
| _version_ |
1764820487192444929 |