z-logo
Premium
Circle graph obstructions under pivoting
Author(s) -
Geelen Jim,
Oum Sangil
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20363
Subject(s) - combinatorics , corollary , circle graph , mathematics , outerplanar graph , discrete mathematics , graph , pathwidth , line graph
A circle graph is the intersection graph of a set of chords of a circle. The class of circle graphs is closed under pivot‐minors. We determine the pivot‐minor‐minimal non‐circle‐graphs; there are 15 obstructions. These obstructions are found, by computer search, as a corollary to Bouchet's characterization of circle graphs under local complementation. Our characterization generalizes Kuratowski's Theorem. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 1‐11, 2009

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom