Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-06T08:00:40.944Z Has data issue: false hasContentIssue false

Operations Which Preserve Path-Width at Most Two

Published online by Cambridge University Press:  02 October 2001

JÁNOS BARÁT
Affiliation:
Bolyai Institute, University of Szeged, Aradi vértanúk tere 1, Szeged, 6720 Hungary (e-mail: jbarat@math.u-szeged.hu, hajnal@math.u-szeged.hu)
PÉTER HAJNAL
Affiliation:
Bolyai Institute, University of Szeged, Aradi vértanúk tere 1, Szeged, 6720 Hungary (e-mail: jbarat@math.u-szeged.hu, hajnal@math.u-szeged.hu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The number of excluded minors for the class of graphs with path-width at most two is very large. To give a practical characterization of the obstructions, we introduce some operations which preserve path-width at most two. We give a list of ten graphs such that any graph with path-width more than two can be reduced – by taking minors and applying our operations – to one of the graphs on our list. We think that our operations and excluded substructures give a far more transparent description of the class of graphs with path-width at most two than Kinnersley and Langston's characterization by 110 excluded minors (see [4]).

Information

Type
Research Article
Copyright
2001 Cambridge University Press