Excluding a large theta graph

DOI10.1016/J.JCTB.2018.03.002zbMATH Open1391.05238arXiv1609.01221OpenAlexW2963342243WikidataQ130121312 ScholiaQ130121312MaRDI QIDQ723880FDOQ723880

Authors: Guoli Ding, Emily A. Marshall 

Publication date: 24 July 2018

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: A theta graph, denoted $het{a}_{a,b,c}$, is a graph of order $a+b+c-1$ consisting of a pair of vertices and three independent paths between them of lengths $a$, $b$, and $c$. We provide a complete characterization of graphs that do not contain a large $het{a}_{a,b,c}$ as a topological minor. More specifically, we describe the structure of $het{a}_{1,2,t}$-, $het{a}_{2,2,t}$-, $het{a}_{1,t,t}$-, $het{a}_{2,t,t}$-, and $het{a}_{t,t,t}$-free graphs where $t$ is large. The main result is a characterization of $het{a}_{t,t,t}$-free graphs for large $t$. The $3$-connected $het{a}_{t,t,t}$-free graphs are formed by $3$-summing graphs without a long path to certain planar graphs. The $2$-connected $het{a}_{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.

Full work available at URL: https://arxiv.org/abs/1609.01221

Recommendations

• Turán numbers of theta graphs
• Minors in graphs of large \(\theta_r\)-girth
• The extremal function for three disjoint theta graphs.
• SUFFICIENT CONDITION FOR THE EXISTENCE OF THREE DISJOINT THETA GRAPHS
• Graphs without theta subgraphs

zbMATH Keywords

graph minorstheta graphs

Mathematics Subject Classification ID

Graph minors (05C83)

Cites Work

• Graph theory
• Graphs on surfaces
• Graph minors. V. Excluding a planar graph
• Graph minors. I. Excluding a forest
• Graph minors. IX: Disjoint crossed paths
• Graph minors. XVI: Excluding a non-planar graph
• Unavoidable minors of large 3-connected binary matroids
• Title not available (Why is that?)
• Excluding a long double path minor
• Large \(W_k\)- or \(K_{3,t}\)-minors in 3-connected graphs

Cited In (1)

• Minors in graphs of large \(\theta_r\)-girth

This page was built for publication: Excluding a large theta graph

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