Fractional Colouring and Hadwiger's Conjecture

Bruce Reed, Paul Seymour

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

LetGbe a loopless graph with noKp+1minor. We prove that the "fractional chromatic number" ofGis at most 2p; that is, it is possible to assign a rationalq(S)≥0 to every stable setS⊆V(G) so that ∑S∋vq(S)=1 for every vertexv, and ∑Sq(S)≤2p.

Original languageEnglish (US)
Pages (from-to)147-152
Number of pages6
JournalJournal of Combinatorial Theory. Series B
Volume74
Issue number2
DOIs
StatePublished - Nov 1 1998

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Fractional Colouring and Hadwiger's Conjecture'. Together they form a unique fingerprint.

Cite this