Skip to main content
MathOverflow

Return to Question

Notice removed Draw attention by Jimmy Dillies
Bounty Ended with Ian Agol's answer chosen by Jimmy Dillies
Notice added Draw attention by Jimmy Dillies
Bounty Started worth 50 reputation by Jimmy Dillies
The title clearly was too general. I made the *question* in the OP the new title. To speak of the 'length of a component' just *happened* to be sensical here, yet sounds incorrect.
Source Link
edit approved Aug 23, 2017 at 9:01
Peter Heinig
edit approved Aug 23, 2017 at 9:01
Peter Heinig
  • 6.1k
  • 1
  • 27
  • 47

Example of Does every finite bridgeless cubic planar simple undirected graph withadmit a 2 factor-factorization with at most two components each of which has even order?

Consider simple bridgeless cubic planar graphs. Does each such graph admit a 2-factorization with 2 (or less) components each of which has even length? (If not, does anyone know of an counter-example?)

Stated otherwise, each simple bridgeless cubic planar graph is either Hamiltonian or admits a 2-factorization each of which component has even length. Is there an upper bound of the number of components?

  • Does each such graph admit a 2-factorization with $\leq 2$ components each of which has even order?

  • If not, does anyone know of an counterexample?

  • More generally: each simple bridgeless cubic planar graph is either Hamiltonian or admits a 2-factorization each of which component has even order. But is there an upper bound of the number of these components?

Example of graph with 2 factor

Consider simple bridgeless cubic planar graphs. Does each such graph admit a 2-factorization with 2 (or less) components each of which has even length? (If not, does anyone know of an counter-example?)

Stated otherwise, each simple bridgeless cubic planar graph is either Hamiltonian or admits a 2-factorization each of which component has even length. Is there an upper bound of the number of components?

Does every finite bridgeless cubic planar simple undirected graph admit a 2-factorization with at most two components each of which has even order?

Consider simple bridgeless cubic planar graphs.

  • Does each such graph admit a 2-factorization with $\leq 2$ components each of which has even order?

  • If not, does anyone know of an counterexample?

  • More generally: each simple bridgeless cubic planar graph is either Hamiltonian or admits a 2-factorization each of which component has even order. But is there an upper bound of the number of these components?

Source Link
Jimmy Dillies
Jimmy Dillies
  • 443
  • 2
  • 15

Example of graph with 2 factor

Consider simple bridgeless cubic planar graphs. Does each such graph admit a 2-factorization with 2 (or less) components each of which has even length? (If not, does anyone know of an counter-example?)

Stated otherwise, each simple bridgeless cubic planar graph is either Hamiltonian or admits a 2-factorization each of which component has even length. Is there an upper bound of the number of components?