✦ LIBER ✦

Interval matroids and graphs

✍ Scribed by F. Jaeger

Publisher: Elsevier Science
Year: 1979
Tongue: English
Weight: 519 KB
Volume: 27
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(79)90167-5

No coin nor oath required. For personal study only.

✦ Synopsis

A base of the cycle space of a binary matroid M on E is said to be convex if its elements can be totally ordered in such a way that for every e E E tk set of elements of the base containing e is an interval. 'Ure show that a binary matroid is cographic iff it has a convex base of cycles; equivalently, gr:lphic matroids can be represented as "interval matroids" (matroids associated in a natural way to interval systems). As a consequence, we obtain characterizations of planar graphs and cubic cyclically-4-edge-connected planar graphs in terms of convex bases of cycles.

📜 SIMILAR VOLUMES

Interval graphs and interval orders

✍ Peter C. Fishburn 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 949 KB

This paper explores the intimate connection between finite interval graphs and interval orders. Special attention is given to the family of interval orders that agree with, or provide representations of, an interval graph. Two characterizations (one by P. Hanlon) of interval graphs with essentially

Frame Matroids and Biased Graphs

✍ Thomas Zaslavsky 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 165 KB

A frame matroid is any submatroid of a matroid in which cach point belongs to a line spanned by a fixed basis. A biased graph is a graph with certain polygons called balanced, no theta graph containing exactly two balanced polygons. We prove that certain matroids, called bias matroids, of biased gra

On matroids and hierarchial graphs

✍ David Fernández-Baca; Mark A. Williams 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 601 KB

Antipodal graphs and oriented matroids

✍ Komei Fukuda; Keiichi Handa 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 786 KB

A graph is antipodal if, for every vertex c', there exists exactly one vertex V which is not closer to r than every vertex adjacent to 6. In this paper we consider the problem of characterizing tope graphs of oriented matroids, which constitute a broad class of antipodal graphs. One of the results i

Open-interval graphs versus closed-inter

Open-interval graphs versus closed-interval graphs

✍ P. Frankl; H. Maehara 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 218 KB

A graph G = (V, E) is said to be represented by a family F of nonempty sets if there is a bijection f:V--\*F such that uv ~E if and only iff(u)Nf(v)q=~. It is proved that if G is a countable graph then G can be represented by open intervals on the real line if and only if G can be represented by clo

Chordal graphs, interval graphs, and wqo

✍ Ding, Guoli 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 240 KB 👁 1 views

Let be the induced-minor relation. It is shown that, for every t, all chordal graphs of clique number at most t are well-quasi-ordered by . On the other hand, if the bound on clique number is dropped, even the class of interval graphs is not well-quasi-ordered by .