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

Maria Chudnovsky, Alexandra Ovetsky Fradkin

Research output: Contribution to journalArticle

8 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 languageEnglish (US)
Pages (from-to)259-278
Number of pages20
JournalJournal of Graph Theory
Volume63
Issue number4
DOIs
StatePublished - Apr 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Claw-free graphs
  • Clique minors
  • Coloring
  • Hadwiger's conjecture

Fingerprint Dive into the research topics of 'An approximate version of Hadwiger's conjecture for graphs claw-free'. Together they form a unique fingerprint.

  • Cite this