Forbidden Subgraph Characterization of Quasi-line Graphs

2015/10/23 by Medha Dhurandhar, Dhurandhar, Medha
Computer Science · Engineering · Mathematics · #05C #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO #msc:05C

paper · pdf · doi:10.48550/arxiv.1510.06839

2

arxiv created 2015/10/23 · openalex publication_date 2015/10/23 · arxiv updated 2015/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Here in particular, we give a characterization of Quasi-line Graphs in terms of forbidden induced subgraphs. In general, we prove a necessary and sufficient condition for a graph to be a union of two cliques.

Related

• A forbidden pair for quasi 5-contractible edges
• Characterization by forbidden induced subgraphs of some subclasses of chordal graphs
• Line graphs of Multi-Graphs and the forbidden graph E₆
• Forbidden pairs and the existence of a dominating cycle
• Forbidden induced subgraphs in iterative higher order line graphs