Affordable Access

Publisher Website

On minimal non [h,2,1] graphs

Authors
Journal
Electronic Notes in Discrete Mathematics
1571-0653
Publisher
Elsevier
Publication Date
Volume
44
Identifiers
DOI: 10.1016/j.endm.2013.10.018
Keywords
  • Intersection Graphs
  • Representations On Trees
  • Forbidden Subgraphs

Abstract

Abstract 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]. The classes [h,2,1] are closed by taking induced subgraphs, therefore each one can be characterized by a family of minimal forbidden induced subgraphs. In this paper we associate the minimal forbidden induced subgraphs for [h,2,1] which are VPT with (color) 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].

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Nonradiative process induced by external magnetic...

on Chemical Physics Letters Jan 01, 1993

Ab initio MO studies on the photodissociation of C...

on Chemical Physics Letters Jan 01, 1996
More articles like this..