Fractional Colouring and Hadwiger's Conjecture

Bruce Reed; Paul Seymour

doi:10.1006/jctb.1998.1835

Fractional Colouring and Hadwiger's Conjecture

Bruce Reed, Paul Seymour

Mathematics

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

30 Scopus citations

Abstract

LetGbe a loopless graph with noK_p+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 language	English (US)
Pages (from-to)	147-152
Number of pages	6
Journal	Journal of Combinatorial Theory. Series B
Volume	74
Issue number	2
DOIs	https://doi.org/10.1006/jctb.1998.1835
State	Published - Nov 1998

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1998.1835

Cite this

@article{35d057fb791e4312bd9a1fe5cde033c5,

title = "Fractional Colouring and Hadwiger's Conjecture",

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

author = "Bruce Reed and Paul Seymour",

note = "Funding Information: * This research was supported by the ONR under Grant N00014-97-1-0512 and the NSF under Grant DMS 9701598.",

year = "1998",

month = nov,

doi = "10.1006/jctb.1998.1835",

language = "English (US)",

volume = "74",

pages = "147--152",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Fractional Colouring and Hadwiger's Conjecture

AU - Reed, Bruce

AU - Seymour, Paul

N1 - Funding Information: * This research was supported by the ONR under Grant N00014-97-1-0512 and the NSF under Grant DMS 9701598.

PY - 1998/11

Y1 - 1998/11

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

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

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

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

U2 - 10.1006/jctb.1998.1835

DO - 10.1006/jctb.1998.1835

M3 - Article

AN - SCOPUS:0040086277

SN - 0095-8956

VL - 74

SP - 147

EP - 152

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -

Fractional Colouring and Hadwiger's Conjecture

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this