Edge colorings and circular flows on regular graphs
Davide Mattiolo, Eckhard Steffen · Journal of Graph Theory · 2021
Abstract Let be the circular flow number of a bridgeless graph . By Steffen it was proved that, for a bridgeless ‐regular graph , where is a positive integer, if and only if has a perfect matching such that is bipartite. This implies that is a class 1 graph. For , all graphs with circular flow number bigger than 4 are class 2 graphs. We show that, for all , . This was conjectured to be true by Steffen. Moreover we prove that, for all , is a ‐regular class 1 graph with no perfect matching whose removal leaves a bipartite graph. We further disprove the conjecture that every ‐regular class 1 graph has circular flow number at most .