The Maximum Chromatic Index of Multigraphs with Given Δ and μ

1. Choudum S.A., Kayathri K.: An extension of Vizing’s adjacency lemma on edge chromatic critical graphs. Discrete Math. 206, 97–103 (1999)

   Article  MathSciNet  MATH  Google Scholar 

2. Edmonds J.: Maximum matching and a polyhedron with 0-1 vertices. J. Res. Nat. Bur. Standards Sect. B 69, 125–130 (1965)

   MathSciNet  MATH  Google Scholar 

3. Favrholdt, L.M., Stiebitz, M., Toft, B.: Graph Edge Colouring: Vizing’s Theorem and Goldberg’s Conjecture. DMF-2006-10-003, IMADA-PP-2006-20, University of Southern Denmark, Odense (2006)

4. Goldberg M.K.: On multigraphs of almost maximal chromatic class (in Russian). Diskret. Analiz. 23, 3–7 (1973)

   Google Scholar 

5. Gupta, R.P.: Studies in the theory of graphs. Ph.D. thesis, Tata Institute of Fundamental Research, Bombay (1967)

6. Haxell, P., McDonald, J.: On characterizing Vizing’s edge colouring bound. Manuscript (2010)

7. Holyer I.: The NP-completeness of edge-colouring. SIAM J. Comput. 10, 718–720 (1981)

   Article  MathSciNet  MATH  Google Scholar 

8. Ore O.: The Four-Colour Problem. Academic Press, New York (1967)

   Google Scholar 

9. Scheide, D.: Kantenfärbungen von Multigraphen. Diplomarbeit, TU Ilmenau (2007)

10. Scheide D., Stiebitz M.: On Vizing’s bound for the chromatic index of a multigraph. Discrete Math. 309, 4920–4925 (2009)

    Article  MathSciNet  MATH  Google Scholar 

11. Seymour P.: On multicolorings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc. Lond. Math. Soc. 38, 423–460 (1979)

    Article  MathSciNet  MATH  Google Scholar 

12. Shannon C.E.: A theorem on coloring the lines of a network. J. Math. Phys. 28, 148–151 (1949)

    MathSciNet  MATH  Google Scholar 

13. Vizing V.: On an estimate of the chromatic class of a p-graph (in Russian). Diskret. Analiz. 3, 25–30 (1964)

    MathSciNet  Google Scholar 

Download references