Variations on the Petersen colouring conjecture (Q2288171)

Summary: The Petersen colouring conjecture states that every bridgeless cubic graph admits an edge-colouring with 5 colours such that for every edge \(e\), the set of colours assigned to the edges adjacent to \(e\) has cardinality either 2 or 4, but not 3. We prove that every bridgeless cubic graph \(G\) admits an edge-colouring with 4 colours such that at most \(\frac{8}{15}\cdot|E(G)|\) edges do not satisfy the above condition. This bound is tight and the Petersen graph is the only connected graph for which the bound cannot be decreased. We obtain such a 4-edge-colouring by using a carefully chosen subset of edges of a perfect matching, and the analysis relies on a simple discharging procedure with essentially no reductions and very few rules.