Abstract | ||
---|---|---|
A theta graph, denoted θa,b,c, is a graph of order a+b+c−1 consisting of a pair of vertices and three internally-disjoint paths between them of lengths a, b, and c. In this paper we study graphs that do not contain a large θa,b,c minor. More specifically, we describe the structure of θ1,2,t-, θ2,2,t-, θ1,t,t-, θ2,t,t-, and θt,t,t-free graphs where t is large. The main result is a characterization of θt,t,t-free graphs for large t. The 3-connected θt,t,t-free graphs are formed by 3-summing graphs without a long path to certain planar graphs. The 2-connected θt,t,t-free graphs are then built up in a similar fashion by 2- and 3-sums. This result implies a well-known theorem of Robertson and Chakravarti on graphs that do not have a bond containing three specified edges. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1016/j.jctb.2018.03.002 | Journal of Combinatorial Theory, Series B |
Keywords | Field | DocType |
Theta graphs,Graph minors | Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Theta graph,Mathematics,Planar graph | Journal |
Volume | ISSN | Citations |
132 | 0095-8956 | 0 |
PageRank | References | Authors |
0.34 | 7 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Guoli Ding | 1 | 444 | 51.58 |
Emily A. Marshall | 2 | 0 | 2.03 |