Skip to main content
MathOverflow

Return to Answer

As explained on the linked page, the result is known for cubic graphs; it is the non-cubic case that remains open.
Source Link
edit approved Jun 21, 2018 at 1:18
lambda
edit approved Jun 21, 2018 at 1:18
lambda
  • 1.4k
  • 1
  • 14
  • 20

Here are two:

Recall that the four colour theorem is equivalent to the statement that bridgeless cubic planar graphs are three-edge-colourable.

There is Tutte’s three-edge-colouring conjecture that every cubic bridgeless graph not containing the Petersen graph as a minor is 3-edge-colourable. This is a theorem now.

A (still open) generalization of this is Tutte’s 4-flow conjecture that every bridgeless cubic graph with no Petersen minor has a nowhere-zero 4-flow.

Another is a conjecture of Seymour about $d$-regular planar (multi-)graphs. This says that every $d$-regular planar graph which satisfies the natural cut condition (for every odd-cardinality subset $X$ of the vertices there are at least $d$ edges between $X$ and the complement) is $d$-edge-colourable. This is still open in general but known for values of $d \leq 8$ (see here).

Here are two:

Recall that the four colour theorem is equivalent to the statement that bridgeless cubic planar graphs are three-edge-colourable.

There is Tutte’s three-edge-colouring conjecture that every cubic bridgeless graph not containing the Petersen graph as a minor is 3-edge-colourable. This is a theorem now.

A (still open) generalization of this is Tutte’s 4-flow conjecture that every bridgeless cubic graph with no Petersen minor has a nowhere-zero 4-flow.

Another is a conjecture of Seymour about $d$-regular planar (multi-)graphs. This says that every $d$-regular planar graph which satisfies the natural cut condition (for every odd-cardinality subset $X$ of the vertices there are at least $d$ edges between $X$ and the complement) is $d$-edge-colourable. This is still open in general but known for values of $d \leq 8$ (see here).

Here are two:

Recall that the four colour theorem is equivalent to the statement that bridgeless cubic planar graphs are three-edge-colourable.

There is Tutte’s three-edge-colouring conjecture that every cubic bridgeless graph not containing the Petersen graph as a minor is 3-edge-colourable. This is a theorem now.

A (still open) generalization of this is Tutte’s 4-flow conjecture that every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow.

Another is a conjecture of Seymour about $d$-regular planar (multi-)graphs. This says that every $d$-regular planar graph which satisfies the natural cut condition (for every odd-cardinality subset $X$ of the vertices there are at least $d$ edges between $X$ and the complement) is $d$-edge-colourable. This is still open in general but known for values of $d \leq 8$ (see here).

Post Made Community Wiki by Todd Trimble
Source Link
Katie Edwards
Katie Edwards
  • 356
  • 3
  • 4

Here are two:

Recall that the four colour theorem is equivalent to the statement that bridgeless cubic planar graphs are three-edge-colourable.

There is Tutte’s three-edge-colouring conjecture that every cubic bridgeless graph not containing the Petersen graph as a minor is 3-edge-colourable. This is a theorem now.

A (still open) generalization of this is Tutte’s 4-flow conjecture that every bridgeless cubic graph with no Petersen minor has a nowhere-zero 4-flow.

Another is a conjecture of Seymour about $d$-regular planar (multi-)graphs. This says that every $d$-regular planar graph which satisfies the natural cut condition (for every odd-cardinality subset $X$ of the vertices there are at least $d$ edges between $X$ and the complement) is $d$-edge-colourable. This is still open in general but known for values of $d \leq 8$ (see here).