Abstract:The Ear Decomposition Theorem of Lovász & Plummer (1986) implies that every matching covered graph (MCG), except $K_2$ and cycles, contains (at least) one of $\theta$ and $K_4$ as a conformal minor. Lovász [Combinatorica 1983] proved the refinement that every nonbipartite MCG contains one of $K_4$ and $\overline{C_6}$. These immediately lead to three problems: characterize (i) $\theta$-free graphs, (ii) $K_4$-free graphs and (iii) $\overline{C_6}$-free graphs. Kothari and Murty [JGT 2016] used the tight cut decomposition theory to solve the planar case of (ii) and (iii); the nonplanar cases are open. In contrast, we exploit a seminal result of Edmonds, Lovász and Pulleyblank [Combinatorica 1982] to obtain a structural characterization of $\theta$-free graphs that immediately places the corresponding decision problem in P. The Petersen graph plays a key role.
We deduce that every $\theta$-free graph has at most $2n-2$ edges, and we characterize the tight examples. Despite being sparse, these graphs are not necessarily planar. In the style of Little [JCT-B 1975], we characterize Pfaffian $\theta$-free graphs in terms of their forbidden conformal minors. Using the works of Robertson, Seymour and Thomas [Ann. of Math. 1999], and of McCuaig [E-JC 2004], we deduce that the Pfaffian recognition problem is in P for $\theta$-free graphs.
Deciding whether a cubic graph is 3-edge-colorable is NP-complete; for $\theta$-free ones, we provide a characterization of those that are 3-edge-colorable, and deduce that the corresponding decision problem lies in P. McCuaig [JGT 2000] characterized 3-connected bipartite cubic graphs each of whose conformal cycles is of length 2 $\pmod{4}$; the 2-connected case is open. We stumbled upon the serendipitous corollary of our main result that each conformal cycle of a 2-connected cubic graph is of length 0 $\pmod{4}$ if and only if it is $\theta$-free.
From: Nishad Kothari [view email]
[v1]
Sun, 7 Jul 2024 05:27:49 UTC (37 KB)
[v2]
Fri, 7 Nov 2025 11:25:42 UTC (37 KB)
[v3]
Sun, 14 Jun 2026 08:24:16 UTC (43 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。