Arthur


Black and White Cycle Conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   Let $ G $ be a cubic graph with a nz-$ 4 $-flow, and let each edge $ e \in E(G) $ satisfying $ G-e $ does not have a nz-$ 4 $-flow be colored black, and let each edge $ e \in E(G) $ satisfying $ G-e $ has a nz-$ 4 $-flow be colored white. Then $ G $ contains a white cycle but not a black cycle.


Used terminology: nz-$ 4 $-flow is the abbrevation for nowhere-zero $ 4 $-flow, a cycle is a connected $ 2 $-regular graph, a cycle is called black (white) if each edge of the cycle is colored black (white).

Keywords: 3-edge-coloring; 4-flow; cubic graphs; removable edge

3-Edge-Coloring Conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   Suppose $ G $ with $ |V(G)|>2 $ is a connected cubic graph admitting a $ 3 $-edge coloring. Then there is an edge $ e \in E(G) $ such that the cubic graph homeomorphic to $ G-e $ has a $ 3 $-edge coloring.

Keywords: 3-edge coloring; 4-flow; removable edge

Cycle Double Covers Containing Predefined 2-Regular Subgraphs ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   Let $ G $ be a $ 2 $-connected cubic graph and let $ S $ be a $ 2 $-regular subgraph such that $ G-E(S) $ is connected. Then $ G $ has a cycle double cover which contains $ S $ (i.e all cycles of $ S $).

Keywords:

3-Decomposition Conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   (3-Decomposition Conjecture) Every connected cubic graph $ G $ has a decomposition into a spanning tree, a family of cycles and a matching.

Keywords: cubic graph

Strong 5-cycle double cover conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   Let $ C $ be a circuit in a bridgeless cubic graph $ G $. Then there is a five cycle double cover of $ G $ such that $ C $ is a subgraph of one of these five cycles.

Keywords: cycle cover

Syndicate content