Affordable Access

Publisher Website

On slim graphs, even pairs, and star-cutsets

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
105
Identifiers
DOI: 10.1016/0012-365x(92)90134-2

Abstract

Abstract Meyniel proved that a graph G is perfect if every odd cycle of G with at least five vertices has at least two chords. A slim graph is any graph obtained from a Meyniel graph by removing all the edges of a given induced subgraph. Hertz introduced slim graphs and proved that they are perfect. We show that Hertz's result can be derived from a deep characterization of Meyniel graphs which is due to Burlet and Fonlupt. Hertz also asked whether every slim graph which is not a clique has an even pair of vertices, and whether every nonbipartite slim graph has a star-cutset. We provide partial solutions to these questions for slim graphs that are derived from i-triangulated graphs and parity graphs.

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

Decomposition of even-hole-free graphs with star c...

on Journal of Combinatorial Theor...

Defending Planar Graphs against Star-Cutsets

on Electronic Notes in Discrete M... Jan 01, 2009

Even pairs in Berge graphs

on Journal of Combinatorial Theor... Jan 01, 2009
More articles like this..