𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hadwiger's conjecture for quasi-line graphs

✍ Scribed by Maria Chudnovsky; Alexandra Ovetsky Fradkin

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
177 KB
Volume
59
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 graph G is not t‐colorable then it contains K~t + 1~ as a minor. This conjecture has been proved for line graphs by Reed and Seymour. We extend their result to all quasi‐line graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 17–33, 2008

📜 SIMILAR VOLUMES

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

Coloring quasi-line graphs
Coloring quasi-line graphs
✍ Maria Chudnovsky; Alexandra Ovetsky 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A graph __G__ is a quasi‐line graph if for every vertex __v__, the set of neighbors of __v__ 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. A theorem of Shannon's implies that if __G__ is a line graph, then

Thomassen's conjecture implies polynomia
Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs
✍ Roman Kužel; Zdeněk Ryjáček; Petr Vrána 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 158 KB

## Abstract A graph __G__ is 1‐Hamilton‐connected if __G__−__x__ is Hamilton‐connected for every __x__∈__V__(__G__), and __G__ is 2‐edge‐Hamilton‐connected if the graph __G__+ __X__ has a hamiltonian cycle containing all edges of __X__ for any __X__⊂__E__^+^(__G__) = {__xy__| __x, y__∈__V__(__G__)}

Bounding χ in terms of ω and Δ for quasi
Bounding χ in terms of ω and Δ for quasi-line graphs
✍ Andrew D. King; Bruce A. Reed 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB

## Abstract A __quasi‐line__ graph is a graph in which the neighborhood of any vertex can be covered by two cliques; every line graph is a quasi‐line graph. Reed conjectured that for any graph __G__, $\chi({{G}}) \leq\left \lceil {{{1}}\over {{2}}}(\Delta({{G}})+{{1}}+\omega({{G}}))\right\rceil$ [R

Tutte's 5-flow conjecture for graphs of
Tutte's 5-flow conjecture for graphs of nonorientable genus 5
✍ Steffen, Eckhard 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 577 KB

We develop four constructions for nowhere-zero 5-flows of 3-regular graphs that satisfy special structural conditions. Using these constructions we show a minimal counterexample to Tutte's 5-Flow Conjecture is of order 244 and therefore every bridgeless graph of nonorientable genus 5 5 has a nowhere