On contact graphs of paths on a grid
share
In this paper we consider Contact graphs of Paths on a Grid (CPG graphs), i.e. graphs for which there exists a family of interiorly disjoint paths on a grid in one-to-one correspondance with their vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. We examine this class from a structural point of view which leads to constant upper bounds on the clique number, the chromatic number and the clique chromatic number. We further investigate the relation between planar graphs and CPG graphs and show that CPG graphs are not necessarily planar and not all planar graphs are CPG. Our class generalizes the well studied class of VCPG graphs.
READ FULL TEXT