A characterization of some graph classes using excluded minors (Q950291)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A characterization of some graph classes using excluded minors |
scientific article |
Statements
A characterization of some graph classes using excluded minors (English)
0 references
22 October 2008
0 references
Some structural characterization of graphs with excluded minors are offered. The excluded minors in different combinations are the \(K_{3, 3}\), \(K_5\), the octahedron graph, the prism and some others that came with the small modifications of the previous ones. The author proves a number of results, part of those new, while the others are simplification of already known ones, see e.g. \textit{G. A. Dirac} [Can. Math. Bull. 6, 183-210 (1963; Zbl 0138.19203)]. The proofs are relatively easy, thanks to the use of the ``Wheel theorem'' of \textit{W. T. Tutte} [Nederl. Akad. Wet., Proc., Ser. A 64, 441-455 (1961; Zbl 0101.40903)], and its strengthening by \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 28, 305-359 (1980; Zbl 0443.05027)].
0 references
excluded minors
0 references
\(\leq k\)-sum of graphs
0 references
tree width of a graph
0 references