Name
Abstract | ||
|---|---|---|
Tree-width and path-width are two important graph parameters introduced by Robertson and Seymour in their famous Graph Minors project. For a fixed positive integer k, the classes of graphs of tree-width at most k, and path-width at most k, are both minor-closed. However, their complete characterizations in terms of excluded minors are known only for k <= 3 for tree-width, and for k <= 2 for path-width. It is known that the number of excluded minors for the class of graphs of path-width <= k is 2 if k = 1; 110 if k = 2; and >= 122 million if k = 3. Barat et. al. [Studia Sci. Math. Hungar., 49 (2012), pp. 211-222] showed that the class of graphs of path-width <= 2, restricted to its 2-connected members, can be characterized by only three excluded minors, and asked whether a similar result may be obtained for 3-connected graphs of path-width <= 3. We answer this question in the affirmative by characterizing this class by five excluded minors. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1137/100800452 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
graph minors,path-width,tree-width | Journal | 27 |
Issue | ISSN | Citations |
3 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guoli Ding | 1 | 444 | 51.58 |
| Stan Dziobiak | 2 | 3 | 2.14 |