Claw-free graphs. VII. Quasi-line graphs

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


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 languageEnglish (US)
Pages (from-to)1267-1294
Number of pages28
JournalJournal of Combinatorial Theory. Series B
Issue number6
StatePublished - Nov 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Claw-free
  • Induced subgraph
  • Quasi-line
  • Structure theorem


Dive into the research topics of 'Claw-free graphs. VII. Quasi-line graphs'. Together they form a unique fingerprint.

Cite this