Vizing's coloring algorithm and the fan number

✍ Scribed by Diego Scheide; Michael Stiebitz

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 199 KB
• Volume: 65
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20469

✦ Synopsis

Abstract

Most upper bounds for the chromatic index of a graph come from algorithms that produce edge colorings. One such algorithm was invented by Vizing [Diskret Analiz 3 (1964), 25–30] in 1964. Vizing's algorithm colors the edges of a graph one at a time and never uses more than Δ+µ colors, where Δ is the maximum degree and µ is the maximum multiplicity, respectively. In general, though, this upper bound of Δ+µ is rather generous. In this paper, we define a new parameter fan(G) in terms of the degrees and the multiplicities of G. We call fan(G) the fan number of G. First we show that the fan number can be computed by a polynomial‐time algorithm. Then we prove that the parameter Fan(G)=max{Δ(G), fan(G)} is an upper bound for the chromatic index that can be realized by Vizing's coloring algorithm. Many of the known upper bounds for the chromatic index are also upper bounds for the fan number. Furthermore, we discuss the following question. What is the best (efficiently realizable) upper bound for the chromatic index in terms of Δ and µ ? Goldberg's Conjecture supports the conjecture that χ′+1 is the best efficiently realizable upper bound for χ′ at all provided that P≠NP. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 115–138, 2010