Claw-free graphs. VII. Quasi-line graphs

Maria Chudnovsky; Paul Seymour

doi:10.1016/j.jctb.2012.07.005

Claw-free graphs. VII. Quasi-line graphs

Maria Chudnovsky, Paul Seymour

Mathematics

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

18 Scopus citations

Abstract

A graph is a quasi-line graph if for every vertex v, the set of neighbours of v is expressible as the union of two cliques. Such graphs are more general than line graphs, but less general than claw-free graphs. Here we give a construction for all quasi-line graphs; it turns out that there are basically two kinds of connected quasi-line graphs, one a generalization of line graphs, and the other a subclass of circular arc graphs.

Original language	English (US)
Pages (from-to)	1267-1294
Number of pages	28
Journal	Journal of Combinatorial Theory. Series B
Volume	102
Issue number	6
DOIs	https://doi.org/10.1016/j.jctb.2012.07.005
State	Published - Nov 2012

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Claw-free
Induced subgraph
Quasi-line
Structure theorem

Access to Document

10.1016/j.jctb.2012.07.005

Cite this

@article{13a54b3ddd914598a8200da64a47760b,

title = "Claw-free graphs. VII. Quasi-line graphs",

abstract = "A graph is a quasi-line graph if for every vertex v, the set of neighbours of v is expressible as the union of two cliques. Such graphs are more general than line graphs, but less general than claw-free graphs. Here we give a construction for all quasi-line graphs; it turns out that there are basically two kinds of connected quasi-line graphs, one a generalization of line graphs, and the other a subclass of circular arc graphs.",

keywords = "Claw-free, Induced subgraph, Quasi-line, Structure theorem",

author = "Maria Chudnovsky and Paul Seymour",

note = "Funding Information: 1 This research was partially conducted while the author served as a Clay Mathematics Institute Research Fellow at Princeton University, and partially supported by NSF grant DMS-0758364. 2 Supported by ONR grant N00014-10-1-0680 and NSF grant DMS-0901075.",

year = "2012",

month = nov,

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

language = "English (US)",

volume = "102",

pages = "1267--1294",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "6",

}

TY - JOUR

T1 - Claw-free graphs. VII. Quasi-line graphs

AU - Chudnovsky, Maria

AU - Seymour, Paul

N1 - Funding Information: 1 This research was partially conducted while the author served as a Clay Mathematics Institute Research Fellow at Princeton University, and partially supported by NSF grant DMS-0758364. 2 Supported by ONR grant N00014-10-1-0680 and NSF grant DMS-0901075.

PY - 2012/11

Y1 - 2012/11

N2 - A graph is a quasi-line graph if for every vertex v, the set of neighbours of v is expressible as the union of two cliques. Such graphs are more general than line graphs, but less general than claw-free graphs. Here we give a construction for all quasi-line graphs; it turns out that there are basically two kinds of connected quasi-line graphs, one a generalization of line graphs, and the other a subclass of circular arc graphs.

AB - A graph is a quasi-line graph if for every vertex v, the set of neighbours of v is expressible as the union of two cliques. Such graphs are more general than line graphs, but less general than claw-free graphs. Here we give a construction for all quasi-line graphs; it turns out that there are basically two kinds of connected quasi-line graphs, one a generalization of line graphs, and the other a subclass of circular arc graphs.

KW - Claw-free

KW - Induced subgraph

KW - Quasi-line

KW - Structure theorem

UR - https://www.scopus.com/pages/publications/84868710830

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

U2 - 10.1016/j.jctb.2012.07.005

DO - 10.1016/j.jctb.2012.07.005

M3 - Article

AN - SCOPUS:84868710830

SN - 0095-8956

VL - 102

SP - 1267

EP - 1294

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 6

ER -

Claw-free graphs. VII. Quasi-line graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this