Hadwiger's conjecture for quasi-line graphs

Maria Chudnovsky; Alexandra Ovetsky Fradkin

doi:10.1002/jgt.20321

Hadwiger's conjecture for quasi-line graphs

Maria Chudnovsky, Alexandra Ovetsky Fradkin

Research output: Contribution to journal › Article › peer-review

17 Scopus citations

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.

Original language	English (US)
Pages (from-to)	17-33
Number of pages	17
Journal	Journal of Graph Theory
Volume	59
Issue number	1
DOIs	https://doi.org/10.1002/jgt.20321
State	Published - Sep 2008
Externally published	Yes

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

Claw-free graphs
Hadwiger's conjecture
Minors

Access to Document

10.1002/jgt.20321

Cite this

@article{57c47a5b007f4956b73f0b855ac5845f,

title = "Hadwiger's conjecture for quasi-line graphs",

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 Kt+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.",

keywords = "Claw-free graphs, Hadwiger's conjecture, Minors",

author = "Maria Chudnovsky and Fradkin, {Alexandra Ovetsky}",

year = "2008",

month = sep,

doi = "10.1002/jgt.20321",

language = "English (US)",

volume = "59",

pages = "17--33",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - Hadwiger's conjecture for quasi-line graphs

AU - Chudnovsky, Maria

AU - Fradkin, Alexandra Ovetsky

PY - 2008/9

Y1 - 2008/9

N2 - 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 Kt+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.

AB - 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 Kt+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.

KW - Claw-free graphs

KW - Hadwiger's conjecture

KW - Minors

UR - http://www.scopus.com/inward/record.url?scp=51049085857&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51049085857&partnerID=8YFLogxK

U2 - 10.1002/jgt.20321

DO - 10.1002/jgt.20321

M3 - Article

AN - SCOPUS:51049085857

SN - 0364-9024

VL - 59

SP - 17

EP - 33

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

Hadwiger's conjecture for quasi-line graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this