An upper bound on clique coloring of B1-EPGt graphs

VITOR DE LUCA; MARÍA PÍA MAZZOLENI; FABIANO OLIVEIRA; JAYME SZWARCFITER

Congreso; EURO 2022; 2022

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. The approaches for solving clique coloring can be very different from those for ordinary vertex coloring. The main reason is that clique coloring is not a hereditary property: it is possible that a graph is k-clique-colorable, but it has an induced subgraph that is not. Another difference is that even a 2-clique colorable graph can contain an arbitrarily large clique. However, clique coloring shares similarities with vertex coloring. For example, every k-coloring is also a k-clique coloring. Moreover, the clique number and the clique chromatic number of G coincide if G is triangle-free. The decision problem of clique-coloring on general graphs is coNP-complete, and NP-complete on graphs with maximum degree 3.We study the clique coloring problem in the context of the edge intersection graphs of paths on a triangular grid (EPGt graphs). These graphs generalize the well-known intersection graphs of paths on a rectangular grid (EPG graphs). A motivation for studying EPGt graphs comes from circuit layout problems. The triangular grid has been studied in the context of the channel assignment problem with separation (CAPS).Similarly to EPG graphs, a turn of a path at a grid point is called a bend. A graph is Bk-EPGt if each path of its EPGt model has at most k bends. We prove that B1-EPGt graphs are 7-clique colorable.