Claw-free graphs. III. Circular interval graphs

Research output: Contribution to journalArticle

22 Scopus citations

Abstract

Construct a graph as follows. Take a circle, and a collection of intervals from it, no three of which have union the entire circle; take a finite set of points V from the circle; and make a graph with vertex set V in which two vertices are adjacent if they both belong to one of the intervals. Such graphs are "long circular interval graphs," and they form an important subclass of the class of all claw-free graphs. In this paper we characterize them by excluded induced subgraphs. This is a step towards the main goal of this series, to find a structural characterization of all claw-free graphs. This paper also gives an analysis of the connected claw-free graphs G with a clique the deletion of which disconnects G into two parts both with at least two vertices.

Original languageEnglish (US)
Pages (from-to)812-834
Number of pages23
JournalJournal of Combinatorial Theory. Series B
Volume98
Issue number4
DOIs
StatePublished - Jul 1 2008

All Science Journal Classification (ASJC) codes

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

Keywords

  • Claw-free
  • Graph
  • Induced subgraph
  • Interval graph

Fingerprint Dive into the research topics of 'Claw-free graphs. III. Circular interval graphs'. Together they form a unique fingerprint.

  • Cite this