Claw-free graphs. V. Global structure

Maria Chudnovsky; Paul Seymour

doi:10.1016/j.jctb.2008.03.002

Claw-free graphs. V. Global structure

Maria Chudnovsky, Paul Seymour

Mathematics

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

65 Scopus citations

Abstract

A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. In earlier papers of this series we proved that every claw-free graph either belongs to one of several basic classes that we described explicitly, or admits one of a few kinds of decomposition. In this paper we convert this "decomposition" theorem into a theorem describing the global structure of claw-free graphs.

Original language	English (US)
Pages (from-to)	1373-1410
Number of pages	38
Journal	Journal of Combinatorial Theory. Series B
Volume	98
Issue number	6
DOIs	https://doi.org/10.1016/j.jctb.2008.03.002
State	Published - Nov 2008

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Claw-free graphs
Induced subgraph
Line graphs

Access to Document

10.1016/j.jctb.2008.03.002

Cite this

@article{208f8fa240d147179a6bef16363c7954,

title = "Claw-free graphs. V. Global structure",

abstract = "A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. In earlier papers of this series we proved that every claw-free graph either belongs to one of several basic classes that we described explicitly, or admits one of a few kinds of decomposition. In this paper we convert this {"}decomposition{"} theorem into a theorem describing the global structure of claw-free graphs.",

keywords = "Claw-free graphs, Induced subgraph, Line graphs",

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 = nov,

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

language = "English (US)",

volume = "98",

pages = "1373--1410",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "6",

}

TY - JOUR

T1 - Claw-free graphs. V. Global structure

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/11

Y1 - 2008/11

N2 - A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. In earlier papers of this series we proved that every claw-free graph either belongs to one of several basic classes that we described explicitly, or admits one of a few kinds of decomposition. In this paper we convert this "decomposition" theorem into a theorem describing the global structure of claw-free graphs.

AB - A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. In earlier papers of this series we proved that every claw-free graph either belongs to one of several basic classes that we described explicitly, or admits one of a few kinds of decomposition. In this paper we convert this "decomposition" theorem into a theorem describing the global structure of claw-free graphs.

KW - Claw-free graphs

KW - Induced subgraph

KW - Line graphs

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

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

U2 - 10.1016/j.jctb.2008.03.002

DO - 10.1016/j.jctb.2008.03.002

M3 - Article

AN - SCOPUS:52149093891

SN - 0095-8956

VL - 98

SP - 1373

EP - 1410

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 6

ER -

Claw-free graphs. V. Global structure

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this