Skip to main content
1 of 2

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).