$\hat{I}¸$-free matching covered graphs: characterization and consequences

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 $\hat{I}¸$ 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) $\hat{I}¸$-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 $\hat{I}¸$-free graphs that immediately places the corresponding decision problem in P. The Petersen graph plays a key role. We deduce that every $\hat{I}¸$-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 $\hat{I}¸$-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 $\hat{I}¸$-free graphs. Deciding whether a cubic graph is 3-edge-colorable is NP-complete; for $\hat{I}¸$-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 $(\mathrm{mod}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 $(\mathrm{mod}4)$ if and only if it is $\hat{I}¸$-free.

This work was presented at two editions of Meru Combinatorics Conference: only characterization in 2024 (by Rohinee Joshi), and the entire work in 2026 (by Santhosh Raghul) with a focus on the consequences. It was also presented at ADMA ICDM (in 2026 by Santhosh Raghul), and it received an award. It has also been accepted for presentation at AsiaComb (2026). None of these involve any publications