[HTML][HTML] On a property of minimal triangulations

D Kratsch, H Müller - Discrete mathematics, 2009 - Elsevier
D Kratsch, H Müller
Discrete mathematics, 2009Elsevier
A graph H has the property MT, if for all graphs G, G is H-free if and only if every minimal
(chordal) triangulation of G is H-free. We show that a graph H satisfies property MT if and
only if H is edgeless, H is connected and is an induced subgraph of P5, or H has two
connected components and is an induced subgraph of 2P3. This completes the results of
Parra and Scheffler, who have shown that MT holds for H= Pk, the path on k vertices, if and
only if k⩽ 5 [A. Parra, P. Scheffler, Characterizations and algorithmic applications of chordal …
A graph H has the property MT, if for all graphs G, G is H-free if and only if every minimal (chordal) triangulation of G is H-free. We show that a graph H satisfies property MT if and only if H is edgeless, H is connected and is an induced subgraph of P5, or H has two connected components and is an induced subgraph of 2P3. This completes the results of Parra and Scheffler, who have shown that MT holds for H=Pk, the path on k vertices, if and only if k⩽5 [A. Parra, P. Scheffler, Characterizations and algorithmic applications of chordal graph embeddings, Discrete Applied Mathematics 79 (1997) 171–188], and of Meister, who proved that MT holds for ℓP2, ℓ copies of a P2, if and only if ℓ⩽2 [D. Meister, A complete characterisation of minimal triangulations of 2K2-free graphs, Discrete Mathematics 306 (2006) 3327–3333].
Elsevier
Showing the best result for this search. See all results