๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Chordal characterization of graphic matroids

โœ Scribed by Wiktor Piotrowski

Publisher
Elsevier Science
Year
1988
Tongue
English
Weight
722 KB
Volume
68
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

In this paper we present the characterization of graphic matroids using the concept of a chord. Then we apply this characterization to solve a problem of Szamkolowicz [9].

One of the deepest theorems in the theory of matroids is Tuttes excludedminor characterization of graphic matroids [ 111. The purpose of this paper is to present the characterization of graphic matroids using the concept of a chord. This concept was introduced in [9], and is closely related to the concepts of Z-arcs [6] and bridges [ll]. As a corollary of our theorem we obtain a positive answer to the problem of Szamkoiowicz [9]. For other characterizations of "graphicness" see [2-5, 7, 131. The terminology used but not defined here is defined by elsh [14] and Tutte [ 121.

Let M be a matroid on a finite set E. A connected line L M is a minimal set

๐Ÿ“œ SIMILAR VOLUMES

On Tutt's Characterization of graphic ma
On Tutt's Characterization of graphic matroidsโ€”a graphic proof
โœ A. M. H. Gerards ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 409 KB

## Abstract In this paper we present a relatively simple proof of Tutt's characterization of graphic matroids. The proof uses the notion of โ€˜signed graphโ€™ and it is โ€˜graphicโ€™ in the sense that it can be presented almost entirely by drawing (signed) graphs. ยฉ 1995 John Wiley & Sons, Inc.

Characterizing 3-connected planar graphs
Characterizing 3-connected planar graphs and graphic matroids
โœ Manoel Lemos; Talmage James Reid; Haidong Wu ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 98 KB

## Abstract A wellโ€known result of Tutte states that a 3โ€connected graph __G__ is planar if and only if every edge of __G__ is contained in exactly two induced nonโ€separating circuits. Bixby and Cunningham generalized Tutte's result to binary matroids. We generalize both of these results and give n

A characterization of strongly chordal g
A characterization of strongly chordal graphs
โœ Elias Dahlhaus; Paul D. Manuel; Mirka Miller ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 119 KB

In this paper, we present a simple charactrization of strongly chordal graphs. A chordal graph is strongly chordal if and only if every cycle on six or more vertices has an induced triangle with exactly two edges of the triangle as the chords of the cycle. (~

A characterization of threshold matroids
A characterization of threshold matroids
โœ Rick Giles; Ravindran Kannan ๐Ÿ“‚ Article ๐Ÿ“… 1980 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 370 KB

~bl if and only if for each pair of , subsets R and S of E, such that IR (JSI ~3, either (i) VTcr E-(RUS), (RUT) E ZF+(SUT)E~