𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Partial characterizations of circular-arc graphs

✍ Scribed by F. Bonomo; G. Durán; L.N. Grippo; M.D. Safe

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
224 KB
Volume
61
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A circular‐arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular‐arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to any of the following classes: P~4~ ‐free graphs, paw‐free graphs, claw‐free chordal graphs and diamond‐free graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 289–306, 2009

📜 SIMILAR VOLUMES

Interval bigraphs and circular arc graph
Interval bigraphs and circular arc graphs
✍ Pavol Hell; Jing Huang 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB

## Abstract We prove that the complements of interval bigraphs are precisely those circular arc graphs of clique covering number two, which admit a representation without two arcs covering the whole circle. We give another characterization of interval bigraphs, in terms of a vertex ordering, that w

Efficient algorithms for interval graphs
Efficient algorithms for interval graphs and circular-arc graphs
✍ U. I. Gupta; D. T. Lee; J. Y.-T. Leung 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 476 KB

## Abstract We show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in __O__(__n__ log __n__) time [__O__(__n__) time if the endpoints of the

Well covered simplicial, chordal, and ci
Well covered simplicial, chordal, and circular arc graphs
✍ Prisner, Erich; Topp, Jerzy; Vestergaard, Preben Dahl 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 427 KB 👁 2 views

A graph G is called well covered if every two maximal independent sets of G have the same number of vertices. In this paper, we,characterize well covered simplicial, chordal and circular arc graphs.

A circular-arc characterization of certa
A circular-arc characterization of certain rectilinear drawings
✍ S. K. Stueckle; B. L. Piazza; R. D. Ringeisen 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB

## Abstract In this paper we give a construction that produces exactly those graphs having maximum rectilinear crossing number equal to the subthrackle bound. We then prove a theorem characterizing these graphs in terms of proper circular‐arc graphs. © 1996 John Wiley & Sons, Inc.