scientific article; zbMATH DE number 1560509
Let \(\Delta=\Delta(G)\) and \(q(G)\) be the maximum degree and chromatic index of a multigraph~\(G\) with \(n=n(G)\) vertices and \(m=m(G)\) edges. Clearly, \(q(G)\geq\Delta(G)\). The problem of deciding whether \(q(G)=\Delta(G)\) is known to be NP-complete. M.~K.~Goldberg (1984) conjectured that \[ q(G)=\max_{H\subseteq G} \left\lceil\frac{m(H)}{\left\lfloor\frac{n(H)}{2}\right\rfloor}\right\rceil \] whenever \(q(G)>\Delta(G)+1\). A relaxation of this conjecture for \(q(G)>\frac{11\Delta(G)+8}{10}\) was confirmed by \textit{T.~Nishizeki} and \textit{K.~Kashiwagi} [SIAM J. Discrete Math. 3, No. 3, 391-410 (1990; Zbl 0702.05036)]. In the article under review, a simple proof of this result is provided.
- Achieving maximum chromatic index in multigraphs
- On Vizing's bound for the chromatic index of a multigraph
- On resolving edge colorings in graphs
- Graph edge coloring: a survey
- Chromatic index determined by fractional chromatic index
- An application of matching theory of edge-colourings
- Average degrees of edge-chromatic critical graphs
- Goldberg's conjecture is true for random multigraphs
- Structural properties of edge-chromatic critical multigraphs
- On edge orienting methods for graph coloring
- Edge coloring multigraphs without small dense subsets
- Edge-colorings of some large graphs on alphabets
- On a limit of the method of Tashkinov trees for edge-colouring
- Vizing's coloring algorithm and the fan number
- On characterizing Vizing's edge colouring bound
- On a theorem of Goldberg
- On the $1.1$ Edge-Coloring of Multigraphs
- scientific article; zbMATH DE number 3914343 (Why is no real title available?)
- Densities, matchings, and fractional edge-colorings
- An asymptotic approximation scheme for multigraph edge coloring
- A combined logarithmic bound on the chromatic index of multigraphs
- A brief history of edge-colorings -- with personal reminiscences
- Double Vizing fans in critical class two graphs
- Orientation‐based edge‐colorings and linear arboricity of multigraphs
- Tashkinov-trees: an annotated proof
- Approximating the chromatic index of multigraphs
- Kempe classes and almost bipartite graphs
- Proof of the Goldberg-Seymour conjecture on edge-colorings of multigraphs
- Graph theory. Abstracts from the workshop held January 5--10, 2025
- Graph edge colouring: Tashkinov trees and Goldberg's conjecture
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4527280)
