Claw-free graphs. VII. Quasi-line graphs

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)1267-1294
Number of pages28
JournalJournal of Combinatorial Theory. Series B
Volume102
Issue number6
DOIs
StatePublished - 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

Fingerprint

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

Cite this