Nowhere-zero 3-flows of graphs with prescribed sizes of odd edge cuts

作者：Luo Rong^*; Miao Zhengke; Xu Rui; Zhang Cun Quan

来源：European Journal of Combinatorics, 2014, 36: 7-16.

DOI：10.1016/j.ejc.2013.05.016

The relation between sizes of odd-cycles and chromatic numbers of graphs has been extensively studied. It was conjectured by Bollobas and Erdos (1990)141 and proved by Gyarfas [A. Gyarfas, Graph with k odd cycle lengths, Discrete Math. 103 (1992) 41-481 that if a graph G has k different odd cycle sizes, then the chromatic number of G, x (G) %26lt;= 2k + 2. Recently, Camacho and Schiermeyer [S.M. Camacho, I. Schiermeyer, Colorings of graphs with two consecutive odd cycle lengths, Discrete Math. 309 (2009) 4916-49191 proved that every graph containing only odd cycles of lengths 2k 1 and 2k + 1 is 4-colorable. Wang IS.S. Wang, Structure and coloring of graphs with only small odd cycles, SIAM J. Discrete Math. 22 (2008) 1040-10721 characterizes all 3-colorable graphs whose only odd cycles are 3-cycles and 5-cycles; and Kaiser et al. [T. Kaiser, 0. Ruck, R. Skrekovski, Graphs with odd cycle lengths 5 and 7 are 3-colorable, SIAM J. Discrete Math. 25 (2012) 1069-10881 proved that every graph with odd cycle lengths 5 and 7 is 3-colorable. In this paper, we investigate the dual version of this problem: the relation between integer flows and odd edge cuts (the integer flow problem is a dual version of the vertex coloring problem, and the dual of an odd-cycle is an odd-edge-cut) The main result in this paper shows that, for each odd integer k %26gt; 3, if the size of every odd edge cut of a graph G is in ik, k + 2, .... 3k-2]. then G admits a nowhere-zero 3-flow if and only if G cannot be reduced to three well-defined families of graphs.

• 出版日期2014-2