Edge coloring nearly bipartite graphs |
| |
| Affiliation: | 1. Eindhoven University of Technology, Netherlands;2. University of Bergen, Norway;3. University of Warwick, United Kingdom of Great Britain and Northern Ireland;4. The Institute of Mathematical Sciences, Chennai, India;1. Department of Mathematical Sciences, University of Illinois at Urbana-Champaign, IL, USA;2. Moscow Institute of Physics and Technology, Russian Federation;3. Combinatorics and Optimization Department, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada;4. School of Mathematics, University of Birmingham, Edgbaston, Birmingham, UK;1. University of Florida, Department of Industrial and Systems Engineering, Gainesville, FL 32611, United States;2. Clemson University, Department of Industrial Engineering, Clemson, SC 29634, United States;1. Department of Computer Science, UPC, Jordi Girona Salgado 1-3, 08034 Barcelona, Spain;2. Barcelona Graduate School of Mathematics, UPC, Pau Gargallo 5, 08028 Barcelona, Spain;3. Max-Planck Institut für Informatik, Campus E1 4, 66123 Saarbrücken, Germany |
| |
| Abstract: | We give a simple polynomial time algorithm to compute the chromatic index of graphs which can be made bipartite by deleting a vertex. An analysis of this algorithm shows that for such graphs, the chromatic index is the roundup of the fractional chromatic index. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
