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 correspondence with their vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. Our class generalizes the well studied class of VCPG graphs (see [1]). We examine CPG graphs from a structural point of view which leads to constant upper bounds on the clique number and the chromatic number. Moreover, we investigate the recognition and 3-colorability problems for B-0-CPG, a subclass of CPG. We further show that CPG graphs are not necessarily planar and not all planar graphs are CPG.

On contact graphs of paths on a grid / Deniz, Zakir; Galby, Esther; Munaro, Andrea; Ries, Bernard. - 11282 LNCS:(2018), pp. 317-330. [10.1007/978-3-030-04414-5_22]

On contact graphs of paths on a grid

Andrea Munaro;
2018-01-01

Abstract

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 correspondence with their vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. Our class generalizes the well studied class of VCPG graphs (see [1]). We examine CPG graphs from a structural point of view which leads to constant upper bounds on the clique number and the chromatic number. Moreover, we investigate the recognition and 3-colorability problems for B-0-CPG, a subclass of CPG. We further show that CPG graphs are not necessarily planar and not all planar graphs are CPG.
9783030044138
On contact graphs of paths on a grid / Deniz, Zakir; Galby, Esther; Munaro, Andrea; Ries, Bernard. - 11282 LNCS:(2018), pp. 317-330. [10.1007/978-3-030-04414-5_22]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2934106
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact