Approximating the chromatic index of multigraphs |
| |
Authors: | Guantao Chen Xingxing Yu Wenan Zang |
| |
Institution: | 1.Department of Mathematics and Statistics,Georgia State University,Atlanta,USA;2.School of Mathematics,Georgia Institute of Technology,Atlanta,USA;3.Department of Mathematics,University of Hong Kong,Hong Kong,China |
| |
Abstract: | It is well known that if G is a multigraph then χ′(G)≥χ′*(G):=max {Δ(G),Γ(G)}, where χ′(G) is the chromatic index of G, χ′*(G) is the fractional chromatic index of G, Δ(G) is the maximum degree of G, and Γ(G)=max {2|E(GU])|/(|U|−1):U⊆V(G),|U|≥3, |U| is odd}. The conjecture that χ′(G)≤max {Δ(G)+1,⌈Γ(G)⌉} was made independently by Goldberg (Discret. Anal. 23:3–7, 1973), Anderson (Math. Scand. 40:161–175, 1977), and Seymour (Proc. Lond. Math. Soc. 38:423–460, 1979). Using a probabilistic argument Kahn showed that for any c>0 there exists D>0 such that χ′(G)≤χ′*(G)+c
χ′*(G) when χ′*(G)>D. Nishizeki and Kashiwagi proved this conjecture for multigraphs G with χ′(G)>⌊(11Δ(G)+8)/10⌋; and Scheide recently improved this bound to χ′(G)>⌊(15Δ(G)+12)/14⌋. We prove this conjecture for multigraphs G with
$\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor$\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor
, improving the above mentioned results. As a consequence, for multigraphs G with
$\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2}$\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2}
the answer to a 1964 problem of Vizing is in the affirmative. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|