𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A case of hadwiger's conjecture

✍ Scribed by Michael O. Albertson

Publisher
Elsevier Science
Year
1973
Tongue
English
Weight
127 KB
Volume
4
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we are concerned with vertex colorings, i.e., assignments of integers to the vertices of a graph.

We recall Hadwiger's Conjecture.

Hadwiger's Conjecture. If G is a graph with chromatic number r then G is contractible to K r.

Hadwiger's Conjecture is known to be true for r less than five. In the case of r = 5, it is equivalent to the Four Color Conjecture.

πŸ“œ SIMILAR VOLUMES

Subcontraction-equivalence and Hadwiger'
Subcontraction-equivalence and Hadwiger's conjecture
✍ D. R. Woodall πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 350 KB

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

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

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.