Line Graphs of Helly Hypergraphs
Yury Metelsky, R. I. Tyshkevich · SIAM Journal on Discrete Mathematics · 2003
A natural generalization of the notion of domino introduced and investigated in [T. Kloks, D. Kratsch, and H. Müller, Dominoes, Lecture Notes in Comput. Sci. 903, Springer-Verlag, Berlin, 1995, pp. 106--120] is considered. A graph is called an r-mino if each of its vertices belongs to at most r maximal cliques. The class of r-minoes is denoted ${\cal M}_r.$ Thus ${\cal M}_2$ is the class of dominoes. It is shown that ${\cal M}_r$ coincides with the class of line graphs of Helly hypergraphs with rank at most r. For an arbitrary r, the existence of a finite list of forbidden induced subgraphs characterizing ${\cal M}_r$ is proved. An explicit finite characterization is given for ${\cal M}_3$. An r-mino is called linear if each of its edges belongs to exactly one maximal clique. We prove that the GRAPH 3-COLORABILITY problem remains NP-complete when restricted to linear dominoes with vertex degrees at most 4.