Claw-free graphs. IV. Decomposition theorem

Maria Chudnovsky; Paul Seymour

doi:10.1016/j.jctb.2007.06.007

Claw-free graphs. IV. Decomposition theorem

Maria Chudnovsky, Paul Seymour

Mathematics

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

43 Scopus citations

Abstract

A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. In this series of papers we give a structural description of all claw-free graphs. In this paper, we achieve a major part of that goal; we prove that every claw-free graph either belongs to one of a few basic classes, or admits a decomposition in a useful way.

Original language	English (US)
Pages (from-to)	839-938
Number of pages	100
Journal	Journal of Combinatorial Theory. Series B
Volume	98
Issue number	5
DOIs	https://doi.org/10.1016/j.jctb.2007.06.007
State	Published - Sep 2008

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Claw-free graphs
Induced subgraphs

Access to Document

10.1016/j.jctb.2007.06.007

Cite this

@article{2a4587cdbdd8479f8d5affbc960d8dad,

title = "Claw-free graphs. IV. Decomposition theorem",

abstract = "A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. In this series of papers we give a structural description of all claw-free graphs. In this paper, we achieve a major part of that goal; we prove that every claw-free graph either belongs to one of a few basic classes, or admits a decomposition in a useful way.",

keywords = "Claw-free graphs, Induced subgraphs",

author = "Maria Chudnovsky and Paul Seymour",

note = "Funding Information: E-mail addresses: [email protected] (M. Chudnovsky), [email protected] (P. Seymour). 1 This research was conducted while the author served as a Clay Mathematics Institute Research Fellow at Princeton University. 2 Supported by ONR grant N00014-01-1-0608 and NSF grant DMS-0070912.",

year = "2008",

month = sep,

doi = "10.1016/j.jctb.2007.06.007",

language = "English (US)",

volume = "98",

pages = "839--938",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "5",

}

TY - JOUR

T1 - Claw-free graphs. IV. Decomposition theorem

AU - Chudnovsky, Maria

AU - Seymour, Paul

N1 - Funding Information: E-mail addresses: [email protected] (M. Chudnovsky), [email protected] (P. Seymour). 1 This research was conducted while the author served as a Clay Mathematics Institute Research Fellow at Princeton University. 2 Supported by ONR grant N00014-01-1-0608 and NSF grant DMS-0070912.

PY - 2008/9

Y1 - 2008/9

N2 - A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. In this series of papers we give a structural description of all claw-free graphs. In this paper, we achieve a major part of that goal; we prove that every claw-free graph either belongs to one of a few basic classes, or admits a decomposition in a useful way.

AB - A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. In this series of papers we give a structural description of all claw-free graphs. In this paper, we achieve a major part of that goal; we prove that every claw-free graph either belongs to one of a few basic classes, or admits a decomposition in a useful way.

KW - Claw-free graphs

KW - Induced subgraphs

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

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

U2 - 10.1016/j.jctb.2007.06.007

DO - 10.1016/j.jctb.2007.06.007

M3 - Article

AN - SCOPUS:49749147883

SN - 0095-8956

VL - 98

SP - 839

EP - 938

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 5

ER -

Claw-free graphs. IV. Decomposition theorem

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this