Claw-free graphs. VII. Quasi-line graphs
type: Item
instance of: scholarly article
title: Claw-free graphs. VII. Quasi-line graphs
zbMATH Open document ID: 1258.05055
author: Maria Chudnovsky
author: Paul Seymour
published in: Journal of Combinatorial Theory. Series B
publication date: 2013-01-14T00:00:00Z
review text: The abstract of the paper gives an appropriate short summary of the results: ``A graph is a \textit{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.'' Note that there may be edges between the two complete graphs in the neighbourhood of a vertex in a quasi-line graph. The proofs of the results depend upon a more general object, which the authors have used in previous papers in the series on claw-free graphs, that the authors call ``\textit{trigraphs}''. A \textit{trigraph} \(G\) has a set of vertices \(V\) along with a map \(\theta_G\) from \(V^2\) into \(\{-1, 0, 1\}\) satisfying the following three conditions: {\parindent=7mm \begin{itemize}\item[(1)]\(\theta_G(v,v) = 0\) for all \(v \in V\), \item[(2)]\(\theta_G(u,v) = \theta_G(v, u)\) for all \(u, v \in V\), and \item[(3)]at most one of \(\theta_G(u, v), \theta_G(u, w) = 0\) for all distinct \(u, v, w \in V\). \end{itemize}} The proofs depend on properties of trigraphs proved in previous papers in this series. The classes of quasi-line graphs are defined in terms of classes of trigraphs. [For the preceding six parts see ibid. 97, No.\,6, 867--903 (2007; Zbl 1128.05031), 98, No.\,2, 249--290 (2008; Zbl 1137.05040), 98, No.\,4, 812--834 (2008; Zbl 1158.05035), 98, No.\,5, 839--938 (2008; Zbl 1152.05038), 98, No.\,6, 1373--1410 (2008; Zbl 1196.05043), 100, No.\,6, 560--572 (2010; Zbl 1207.05050).]
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C76
zbMATH DE Number: 6125256
zbMATH Keywords: claw-free
zbMATH Keywords: induced subgraph
zbMATH Keywords: quasi-line
zbMATH Keywords: structure theorem
zbMATH Keywords: trigraphs
reviewed by: Ralph Faudree
MaRDI profile type: Publication
full work available at URL: j.jctb.2012.07.005
OpenAlex ID: W2019761982
cites work: Q3416248
cites work: Claw-free graphs. I: Orientable prismatic graphs
cites work: Claw-free graphs. II: Non-orientable prismatic graphs
cites work: Claw-free graphs. IV: Decomposition theorem
cites work: Claw-free graphs. V. Global structure
DOI: 10.1016/J.JCTB.2012.07.005
description: scientific article; zbMATH DE number 6125256