On edge intersection graphs of paths on a triangular grid: Characterization and clique coloring

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

Conferencia; XXI LATIN IBERO-AMERICAN CONFERENCE ON OPERATIONS RESEARCH; 2022

Universidad de Buenos Aires

We introduce a new class of intersection graphs, the edge intersection graphs of paths on atriangular grid, called EPG\textsubscript{t} graphs. We compare this new class with the well-knownclass of EPG graphs. A turn of a path at a grid point is called a \emph{bend}. An EPG\textsubscript{t}representation in which every path has at most $k$ bends is called a B$_k$-EPG\textsubscript{t}representation and the corresponding graphs are called B$_k$-EPG\textsubscript{t} graphs. Wecharacterize the representation of cliques with three vertices and chordless $4$-cycles in B$_{1}$-EPG\textsubscript{t} representations. We also prove that B$_{1}$-EPG\textsubscript{t} graphs haveStrong Helly number $3$. Furthermore, we consider the problem of clique coloring, that is, coloringthe vertices of a given graph such that no (maximal) clique of size at least two is monocolored. Ingeneral, clique coloring can be a very different problem from ordinary vertex coloring. The maindifference is that clique coloring is not a hereditary property: it is possible that a graph is $k$-cliquecolorable, but it has an induced subgraph that is not. Another difference is that even a $2$-cliquecolorable graph can contain an arbitrarily large clique. However, clique coloring has also somesimilarities with usual 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 it is NP-completeon graphs with maximum degree 3. We prove that B$_{1}$-EPG\textsubscript{t} graphs are $7$-clique colorable.