Claw-free graphs. VII. Quasi-line graphs

被引：18

作者：

Chudnovsky, Maria ^{[1
,2
]}

Seymour, Paul

机构：

[1] Columbia Univ, New York, NY 10027 USA

[2] Princeton Univ, Clay Math Inst, Princeton, NJ 08544 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2012年 / 102卷 / 06期

关键词：

Induced subgraph; Claw-free; Quasi-line; Structure theorem; PRISMATIC GRAPHS;

D O I：

10.1016/j.jctb.2012.07.005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (c) 2012 Elsevier Inc. All rights reserved.

引用

页码：1267 / 1294

页数：28

共 4 条

[1]

Chudnovsky M., 2005, BCC, V327, P153

[2] Claw-free graphs. V. Global structure [J].