A characterization of some graph classes using excluded minors

DOI10.1007/S10998-007-3001-4MaRDI QIDQ950291zbMATH OpenOpenAlexFDO

Authors Janka Chlebíková

Publication date 22 October 2008

Published in Periodica Mathematica Hungarica (Search for Journal in Brave)

Full work available at URL https://researchportal.port.ac.uk/portal/en/publications/a-characterization-of-some-graph-classes-using-excluded-minors(2d0aa654-aec2-423e-9e23-c6c40427e653).html

zbMATH Keywords

\(\leq k\)-sum of graphsexcluded minorstree width of a graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph minors (05C83)

Review text

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)].

Recommendations

• Excluded-minor characterization of apex-outerplanar graphs
• A characterization of graphs with no octahedron minor
• Hall-type results for 3-connected projective graphs
• Graph minors. XVI: Excluding a non-planar graph
• scientific article; zbMATH DE number 1342090

Cites work

• A characterization of partial 3-trees
• An excluded minor theorem for the octahedron
• Bemerkungen zu Hadwigers Vermutung
• Decomposition of regular matroids
• Forbidden minors characterization of partial 3-trees
• Graph minors. III. Planar tree-width
• scientific article; zbMATH DE number 3166039 (Why is no real title available?)
• scientific article; zbMATH DE number 48089 (Why is no real title available?)
• scientific article; zbMATH DE number 1342090 (Why is no real title available?)
• Some Results Concerning the Structure of Graphs
• Über Minimalstrukturen von Graphen, insbesondere von n-fach zusammenhängenden Graphen

Cited in

(9)

• The minor crossing number of graphs with an excluded minor
• On the critical densities of minor-closed classes
• Excluded minors in cubic graphs
• A characterization of graphs with no octahedron minor
• Excluded-minor characterization of apex-outerplanar graphs
• An Excluded Minor Characterization of Seymour Graphs
• Hall-type results for 3-connected projective graphs
• An excluded minor theorem for the Octahedron plus an edge
• A circle criterion for a generalized cross graph in terms of minimal excluded minors

This page was built for publication: A characterization of some graph classes using excluded minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q950291)