2025/11/03 by Davide Mattiolo, Mattiolo, Davide
Computer Science · Mathematics · #05C21 #05C70 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2511.01556
openalex publication_date 2025/11/03 · openalex created_date 2025/11/06 · openalex updated_date 2026/07/28
A set R⊆ E(G) of a graph G is k-removable if G-R has a nowhere-zero k-flow. We prove that every graph G admitting a nowhere-zero 4-flow has a 3-removable subset consisting of at most (1)/(6)|E(G)| edges. This gives a positive answer to a conjecture of M. DeVos, J. McDonald, I. Pivotto, E. Rollová and R. Šámal [3-Flows with large support, J. Comb. Theory Ser. B 144 (2020), 32-80] in the case of graphs admitting a nowhere-zero 4-flow. Moreover, Hoffmann-Ostenhof recently conjectured that every cubic graph with a nowhere-zero 4-flow has a 4-removable edge. Bipartite cubic graphs verify this conjecture. Our result gives an approximation for Hoffmann-Ostenhof's Conjecture in the non-bipartite case. Finally, for cubic graphs, our result implies that every 3-edge-colorable cubic graph G contains a subgraph H whose connected components are either cycles or subdivisions of bipartite cubic graphs, such that |E(H)|≥ (5)/(6)|E(G)|.