Claw-free graphs. VII. Quasi-line graphs (Q1931400)

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).]