✦ LIBER ✦

Subcontraction-equivalence and Hadwiger's conjecture

✍ Scribed by D. R. Woodall

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 350 KB
Volume: 11
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190110210

No coin nor oath required. For personal study only.

✦ Synopsis

The concept of subcontraction-equivalence is defined, and 14 graphtheoretic properties are exhibited that are all subcontraction-equivalent if Hadwiger's conjecture is true. Some subsets of these properties are proved to be subcontraction-equivalent anyway. Hadwiger's conjecture is expressed as the union of three independent and strictly weaker subconlectures. As a first step toward one of these subconjectures, it is proved that a graph that does not have Km+, as a subcontraction must contain an independent set consisting of at least 1 /2(m -1) of its vertices.

📜 SIMILAR VOLUMES

Fractional Colouring and Hadwiger's Conj

Fractional Colouring and Hadwiger's Conjecture

✍ Bruce Reed; Paul Seymour 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 162 KB

Hadwiger's conjecture for quasi-line gra

Hadwiger's conjecture for quasi-line graphs

✍ Maria Chudnovsky; Alexandra Ovetsky Fradkin 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB

## Abstract A graph __G__ is a quasi‐line graph if for every vertex __v__ ∈ __V__(__G__), the set of neighbors of __v__ in __G__ can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. Hadwiger's conjecture states that if a grap

Equivalence of Fleischner's and Thomasse

Equivalence of Fleischner's and Thomassen's Conjectures

✍ Martin Kochol 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 96 KB

We show that conjectures of Thomassen (every 4-connected line graph is hamiltonian) and Fleischner (every cyclically 4-edge-connected cubic graph has either a 3-edge-coloring or a dominating cycle) are equivalent.

Derived Equivalences and Dade's Invarian

Derived Equivalences and Dade's Invariant Conjecture

✍ Andrei Marcus 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 115 KB

An approximate version of Hadwiger's con

An approximate version of Hadwiger's conjecture for claw-free graphs

✍ Maria Chudnovsky; Alexandra Ovetsky Fradkin 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 189 KB

## Abstract Hadwiger's conjecture states that every graph with chromatic number χ has a clique minor of size χ. In this paper we prove a weakened version of this conjecture for the class of claw‐free graphs (graphs that do not have a vertex with three pairwise nonadjacent neighbors). Our main resul

A short proof of a theorem of dirac's ab

A short proof of a theorem of dirac's about hadwiger's conjecture

✍ D. R. Woodall 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 1 views

## Abstract A Short proof is given of the theorem that every grph that does not have __K__~4~ as a subcontraction is properly vertex 3‐colorable.