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

Maria Chudnovsky; Alexandra Ovetsky Fradkin

doi:10.1002/jgt.20425

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

Maria Chudnovsky, Alexandra Ovetsky Fradkin

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

9 Scopus citations

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 result is that a claw-free graph with chromatic number χ has a clique minor of size ⌈2/3χ⌉.

Original language	English (US)
Pages (from-to)	259-278
Number of pages	20
Journal	Journal of Graph Theory
Volume	63
Issue number	4
DOIs	https://doi.org/10.1002/jgt.20425
State	Published - Apr 2010
Externally published	Yes

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

Claw-free graphs
Clique minors
Coloring
Hadwiger's conjecture

Access to Document

10.1002/jgt.20425

Cite this

@article{ce0288fcce5841d98821569b2de9edf1,

title = "An approximate version of Hadwiger's conjecture for graphs claw-free",

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 result is that a claw-free graph with chromatic number χ has a clique minor of size ⌈2/3χ⌉.",

keywords = "Claw-free graphs, Clique minors, Coloring, Hadwiger's conjecture",

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

year = "2010",

month = apr,

doi = "10.1002/jgt.20425",

language = "English (US)",

volume = "63",

pages = "259--278",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

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

AU - Chudnovsky, Maria

AU - Fradkin, Alexandra Ovetsky

PY - 2010/4

Y1 - 2010/4

N2 - 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 result is that a claw-free graph with chromatic number χ has a clique minor of size ⌈2/3χ⌉.

AB - 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 result is that a claw-free graph with chromatic number χ has a clique minor of size ⌈2/3χ⌉.

KW - Claw-free graphs

KW - Clique minors

KW - Coloring

KW - Hadwiger's conjecture

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

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

U2 - 10.1002/jgt.20425

DO - 10.1002/jgt.20425

M3 - Article

AN - SCOPUS:77950202442

SN - 0364-9024

VL - 63

SP - 259

EP - 278

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this