Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Circular chromatic number of planar graphs of large odd girth. | Circular chromatic number of planar graphs of large odd girth Xuding Zhu Department of Applied Mathematics National Sun Yat-sen University Kaohsiung Taiwan 80424 zhu@ Submitted October 17 2000 Accepted June 7 2001. Mathematical Subject Classification 05C15 Abstract It was conjectured by Jaeger that 4k-edge connected graphs admit a 2k 1 k -flow. The restriction of this conjecture to planar graphs is equivalent to the statement that planar graphs of girth at least 4k have circular chromatic number at most 2 1. Even this restricted version of Jaeger s conjecture is largely open. The k 1 case is the well-known Grotzsch 3-colour theorem. This paper proves that for k 2 planar graphs of odd girth at least 8k 3 have circular chromatic number at most 2 1. 1 Introduction Let G be a graph and D an orientation of G. For positive integers k 2d a k d -flow f of D is a mapping that assigns to each edge e of D an integer f e such that i for every vertex x e2E x f e EeEE- x f e 0 and ii for every edge e d If e I k d. Here E x is the set of edges incident to and oriented away from x and E- x is the set of edges incident to and oriented towards x. A graph G is said to admit a k d -flow if G has an orientation D that admits a k d -flow. The following conjecture was proposed by Jaeger 7 8 Conjecture For any integer k 1 every 4k-edge-connected graph admits an 2k 1 k -flow. This research was partially supported by the National Science Council under grant NSC89-2115-M-110-012 THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R25 1 Jaeger s conjecture is very strong. The k 1 case is Tutte s 3-flow conjecture 16 and the k 2 case implies Tutte s 5-flow conjecture 17 . Both the 3-flow conjecture and the 5-flow conjecture are long standing open problems 20 . Many difficult conjectures for flows have been proved for planar graphs. However even restricted to planar graphs Jaeger s conjecture remains largely open. For planar graphs the flow problem can be dualized to a colouring
