Contractible configurations, Z3-connectivity, Z3-flows and triangularly connected graphs
Hong‐Jian Lai, Rui Xu, Cun‐Quan Zhang · 2008
Tutte conjectured that every 4-edge connected graph admits a nowhere-zero Z3-flow and Jaeger, Linial, Payan and Tarsi conjectured that every 5-edge connected graph is Z3-connected. In this paper, we characterize the triangularly connected graphs G that are Γ-connected for any Abelian group Γ with |Γ | ≥ 3. Therefore, these two conjectures are verified for the family of triangularly connected graphs. Let P be a graph theory property. A graph H is a P-contractible if, for every supgraph G of H (i.e. G is a graph containing H as a subgraph), G has the property P if and only if G/H has the property P. This concept is inspired by the following methods and techniques introduced by Catlin, Seymour, Jaeger, Linial, Payan and Tarsi, such as, collapsible graph for supereulerian graphs, Φk-graph in the proof of 6-flow theorem, and group connectivity for integer flows. In this paper, we proved some basic and useful lemmas for P-contractibility: (1) If a graph H is ∗ Partially supported by the National Security Agency under Grants MDA904- 01-1-0022 and MSPR-03G-023. 1 P-contractible, then, for every supgraph G of H, G is P-contractible if and only if G/H is P contractible; (2) a graph H is Z3-connected if and only if it is Z3-flow contractible. 1