On minimal non [h,2,1] graphs

LILIANA ALCÓN; MARISA GUTIERREZ; MARÍA PÍA MAZZOLENI

Córdoba

Simposio; SIO 2013 - 11º Simposio Argentino de Investigación Operativa.; 2013

A graph G is called a VPT graph if it is the vertex intersection graph of a family of paths in a tree.  The class of graphs which admits a VPT representation in a host tree with maximum degree at most h is denoted by [h,2,1]. In \cite{gravril}, it is shown that the problem of recognizing VPTgraphs is polynomial time solvable. In \cite{pia}, it is proved that the problem of deciding whether a given VPT graph belongs to [h,2,1] is NP-complete even when restricted to the class VPT$\cap$ Split without dominated stable vertices. The classes [h,2,1], $h\geq 2$, are closed by taking induced subgraphs, therefore each one can be characterized by a family of minimal forbidden induced subgraphs. Such a family is know only for h=2 \cite{B8} and there are some partial results for h=3 \cite{hugo}. In this paper we associate the minimal forbidden induced subgraphs for [h,2,1] which are VPT with (color) h-critical graphs. We describe how to obtain minimal forbidden induced subgraphs from critical graphs, even more, we show that the family of graphs obtained using our procedure is exactly the family of minimal forbidden induced subgraphs which are VPT, split and have no dominated stable vertices. We conjecture that there are no other VPT minimal forbidden induced subgraphs. We also prove that the minimal forbidden induced subgraphs for [h,2,1] that are VPT graphs belong to the class [h+1,2,1].