𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On slim graphs, even pairs, and star-cutsets

✍ Scribed by Chính T. Hoàng; Frédéric Maffray

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
724 KB
Volume
105
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Hoang, C.T. and F. Maffray, On slim graphs, even pairs, and star-cutsets, Discrete Mathematics 105 (1992) 93-102.

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.

📜 SIMILAR VOLUMES

Even pairs and the strong perfect graph
Even pairs and the strong perfect graph conjecture
✍ Stefan Hougardy 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 130 KB

We will characterize all graphs that have the property that the graph and its complement are minimal even pair free. This characterization allows a new formulation of the Strong Perfect Graph Conjecture. The reader is assumed to be familiar with perfect graphs (see e.g. [2]). A hole is a cycle of l

K4-free graphs with no odd hole: Even pa
K4-free graphs with no odd hole: Even pairs and the circular chromatic number
✍ Yori Zwols 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K 4 -free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K 4 -free graph with no odd hole has

On incidence coloring and star arboricit
On incidence coloring and star arboricity of graphs
✍ Barry Guiduli 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 190 KB

In this note we show that the concept of incidence coloring introduced by Brualdi and Massey [4] is a special case of directed star arboricity, introduced by Agor and Alon ['2]. A conjecture in [4] concerning asymptotics of the incidence coloring number is solved in the negative following an example

On tactical configurations, regular bipa
On tactical configurations, regular bipartite graphs, and (v, k, even)-designs
✍ Harald Gropp 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 795 KB

A report on small regular bipartite graphs is given. Some historical facts are mentioned as well as equivalent combinatorial structures are discussed. In the second part a new combinatorial structure, the (v,k, even/odd)-designs are introduced. Some first results on (v,k, even)-designs for even k ar