✦ LIBER ✦

A proof of a circle graph characterization

✍ Scribed by Emmanuel Gasse

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 266 KB
Volume: 173
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)00068-x

No coin nor oath required. For personal study only.

✦ Synopsis

A circle graph is an intersection graph of a non-empty finite set of chords of a circle. By using a theorem of Bouchet, we redemonstrate easily a result obtained by Naji which characterizes circle graphs by resolving a system of linear equations of GF(2).

The graphs that we consider are simple. A graph G = (V, E) is a circle graph if its set V of vertices bijectively corresponds to a set of chords of a circle, so that two chords cross if and only if the corresponding vertices are adjacent [2, 4 7, 9]. Such a circle with these chords is called a chord diagram associated to G (see the example below). To a graph G = (V, E) with n vertices, we associate the vector space o~(O) isomorphic to GF(2),(,-1). The n(n -1) components of a vector/? in ~(G) are denoted by { fi(x, y): xs V, y~ V, x vay}. The system S(G) linked to G is the system of linear equations composed of three types of equations (El), (E2) and (E3):

📜 SIMILAR VOLUMES

A simple proof of the characterization o

A simple proof of the characterization of antipodal graphs

✍ Garry Johns 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 88 KB

The antipodal graph A(G) of a graph G is defined as the graph on the same vertex set as G with two vertices being adjacent in A(G) if the distance between them in G is the diameter of G. (If G is disconnected then we define &am(G) = co.) Aravamudhan and Rajendran [l, 21 gave the following character

A constructive proof of the circle theor

A constructive proof of the circle theorem

✍ S.D. Nigam; T. Amaranath 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 61 KB

A Short Proof of Guenin's Characterizati

A Short Proof of Guenin's Characterization of Weakly Bipartite Graphs

✍ Alexander Schrijver 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 79 KB

We give a proof of Guenin's theorem characterizing weakly bipartite graphs by not having an odd-K 5 minor. The proof curtails the technical and case-checking parts of Guenin's original proof.

Excluding a bipartite circle graph from

Excluding a bipartite circle graph from line graphs

✍ Sang-il Oum 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 215 KB

## Abstract We prove that, for a fixed bipartite circle graph __H__, all line graphs with sufficiently large rank‐width (or clique‐width) must have a pivot‐minor isomorphic to __H__. To prove this, we introduce graphic delta‐matroids. Graphic delta‐matroids are minors of delta‐matroids of line grap

A short proof thatN3is not a circle cont

A short proof thatN3is not a circle containment order

✍ Glenn H. Hurlbert 📂 Article 📅 1988 🏛 Springer Netherlands 🌐 English ⚖ 100 KB

A partially ordered set P is called a circle containment order provided one can assign to each x e P a circle C x so that x <~ y ¢=~ Cx c\_ Cy. We show that the infinite three-dimensional poset N 3 is not a circle containment order and note that it is still unknown whether or not [n] 3 is such an or

A short proof of Kuratowski's graph plan

A short proof of Kuratowski's graph planarity criterion

✍ Makarychev, Yury 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB 👁 2 views

We present a new short combinatorial proof of the sufficiency part of the well-known Kuratowski's graph planarity criterion. The main steps are to prove that for a minor minimal non-planar graph G and any edge xy: (1) G-x-y does not contain θ-subgraph; (2) G-x-y is homeomorphic to the circle; (3)