2012/10/30 by Luis Goddyn, Goddyn, Luis, Andrea Spencer +1
Mathematics · #05C15 #05C31 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C31
paper · pdf · doi:10.48550/arxiv.1210.7944
14 pages, 1 figure
arxiv created 2012/10/30 · arxiv updated 2012/10/31
It is known that every loopless cubic graph is 4-edge choosable. We prove the following strengthened result. Let G be a planar cubic graph having b cut-edges. There exists a set F of at most 5b/2 edges of G with the following property. For any function L which assigns to each edge of F a set of 4 colours and which assigns to each edge in E(G)-F a set of 3 colours, the graph G has a proper edge colouring where the colour of each edge e belongs to L(e).