Name
Abstract | ||
|---|---|---|
The graph minor structure theorem by Robertson and Seymour shows that every graph that excludes a fixed minor can be constructed by a combination of four ingredients: graphs embedded in a surface of bounded genus, a bounded number of vortices of bounded width, a bounded number of apex vertices, and the clique-sum operation. This paper studies the converse question: What is the maximum order of a complete graph minor in a graph constructed using these four ingredients? Our main result answers this question up to a constant factor. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.jctb.2012.09.001 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
complete graph minor,constant factor,complete graph,graph minor structure theorem,bounded number,fixed minor,converse question,apex vertex,bounded genus,bounded width,clique-sum operation,graph theory,structure theorem,graph minor,graph embedding | Discrete mathematics,Combinatorics,Forbidden graph characterization,Robertson–Seymour theorem,Cubic graph,Null graph,Apex graph,Graph minor,Petersen graph,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
103 | 1 | Journal of Combinatorial Theory, Series B, 103/1:61--74, 2013 |
Citations | PageRank | References |
8 | 0.46 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gwenaël Joret | 1 | 196 | 28.64 |
| David R. Wood | 2 | 1073 | 96.22 |