2024/07/07 by Rohinee Joshi, Joshi, Rohinee, Raghul, Santhosh +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2407.05264
openalex publication_date 2024/07/07 · openalex created_date 2024/07/10 · openalex updated_date 2026/07/28
The Ear Decomposition Theorem of Lovász & Plummer (1986) implies that every matching covered graph (MCG), except K2 and cycles, contains (at least) one of θ and K4 as a conformal minor. Lovász [Combinatorica 1983] proved the refinement that every nonbipartite MCG contains one of K4 and C6. These immediately lead to three problems: characterize (i) θ-free graphs, (ii) K4-free graphs and (iii) C6-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 θ-free graphs that immediately places the corresponding decision problem in P. The Petersen graph plays a key role. We deduce that every θ-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 θ-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 θ-free graphs. Deciding whether a cubic graph is 3-edge-colorable is NP-complete; for θ-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 \pmod4; 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 \pmod4 if and only if it is θ-free.