✦ LIBER ✦

Counterexamples to three conjectures concerning perfect graphs

✍ Scribed by Stefan Hougardy

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 382 KB
Volume: 117
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90338-t

No coin nor oath required. For personal study only.

✦ Synopsis

We will present counterexamples to a conjecture of Hoang on alternately orientable graphs, a conjecture of Hertz and de Werra on even pairs and to a conjecture of Reed on Berge graphs. All these three conjectures are related to perfect graphs.

📜 SIMILAR VOLUMES

A counterexample to a conjecture of meyn

A counterexample to a conjecture of meyniel on kernel-perfect graphs

✍ Hortensia Galeana-Sánchez 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 237 KB

Counterexamples to the edge reconstructi

Counterexamples to the edge reconstruction conjecture for infinite graphs

✍ Carsten Thomassen 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 407 KB

VWtWiCS cd ~~~tl~Jk:lJtJO?I. &JCJdty of .%iiJthYmcJtics. ~hatwrsrty of W&ur

Counterexamples to faudree and schelp's

Counterexamples to faudree and schelp's conjecture on hamiltonian-connected graphs

✍ Carsten Thomassen 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 291 KB

## Abstract Faudree and Schelp conjectured that for any two vertices __x, y__ in a Hamiltonian‐connected graph __G__ and for any integer __k__, where __n__/2 ⩽ __k__ ⩽ __n__ − 1, __G__ has a path of length __k__ connecting __x__ and __y__. However, we show in this paper that there are infinitely ma

Combinatorial designs related to the str

Combinatorial designs related to the strong perfect graph conjecture

✍ V. Chvátal; R.L. Graham; A.F. Perold; S.H. Whitesides 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 842 KB

Simple solutions of these matrix equations are easy to find; we describe ways of cortstructing rather messy ones. Our investigations are motivated by an intimate relationship between the pairs X, Y and minimal imperfect graphs.

Counterexamples to a conjecture about bo

Counterexamples to a conjecture about bottlenecks in non-Tait-colourable cubic graphs

✍ Eckhard Steffen 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 47 KB

We follow the terminology and notion of . By a well known theorem of Vizing it follows that the chromatic index z'(G) of a cubic graph G is 3 or 4. If z'(G) = 4 we say that G is non-Tait-colourable. Holroyd and Loupekine [1] defined a bottleneck in a non-Tait-colourable cubic graph G =

A counterexample to a conjecture on the

A counterexample to a conjecture on the bondage number of a graph

✍ Ulrich Teschner 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 113 KB

The bondage number h(G) of a nonempty graph G was first introduced by Fink, Jacobson, Kinch and Roberts in [3]. They generalized a former approach to domination-critical graphs, In their publication they conjectured that b(G)<d(G)+ 1 for any nonempty graph G.