Open Problem Garden - Odd cycles and low oddness - Comments

Let be a bridgeless cubic (re: Odd cycles and low oddness)

Anonymous — Tue, 13 Dec 2011 16:50:10 +0100

Let be a bridgeless cubic graph. The oddness of a 2-factor is the number of odd circuits of . The oddness of is the smallest oddness over all 2-factors. For example, a 3-edge-colorable cubic graph has oddness zero and the Petersen graph has oddness two.

This conecture is false. (re: Odd cycles and low oddness)

Anonymous — Fri, 02 Jul 2010 06:43:39 +0200

Case 2: If all of the edges of the form are contained in the same cycle in a 2-factor of , then replacing the edges with the edges converts this 2-factor of into a 2-factor of disjoint copies of the Petersen graph. Hence, when restricted to each , the 2-factor of consists of a cycle with 5 vertices and a -path containing a total of 5 vertices. These paths must be joined together through the edges of the form creating a cycle of length 5n. Hence, in this case the 2-factor of contains cycles of length 5 and one cycle of length 5n (which is odd).

Now, is a bridgeless cubic graph whose 2-factors contain only odd cycles, but no 2-factor of contains fewer than cycles.

This conjecture is false. (re: Odd cycles and low oddness)

Anonymous — Tue, 29 Jun 2010 22:33:14 +0200

For odd and , let be the graph obtained by deleting an edge, say , from the Petersen graph. Define to be the graph obtained by joining vertex and vertex with an edge (with subscripts reduced modulo ). For each , the set is an edge cut. Hence, in any 2-factor of , either none of the edges of the form are contained in a cycle, or all of them are contained in the same cycle.

Case 1: If none of the edges described above are contained in a cycle of a 2-factor of , then this 2-factor contains a 2-factor of for each . These 2-factors are also 2-factors of the graphs , that is, each is a 2-factor of the Petersen graph. Each 2-factor of the Petersen graph consists of two cycles of 5 vertices, hence, any such 2-factor of contains cycles of odd length.

Case 2: See the comment below.

what is oddness (re: Odd cycles and low oddness)

Anonymous — Sat, 16 Jan 2010 09:49:43 +0100

The notion of oddness of a graph requires explanation.

Odd cycles and low oddness

Gagik — Fri, 15 Jan 2010 19:07:33 +0100

Author(s):

Subject: Graph Theory

Conjecture If in a bridgeless cubic graph the cycles of any -factor are odd, then , where denotes the oddness of the graph , that is, the minimum number of odd cycles in a -factor of .