Fast algorithms for Vizing's theorem on bounded degree graphs

DOI10.1016/J.JCTB.2025.07.002MaRDI QIDQ6930173zbMATH OpenFDO

Authors Anton Bernshteyn, Abhishek Dhawan

Publication date 16 September 2025

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCTB.2025.07.002

zbMATH Keywords

\( \mathsf{LOCAL}\) modeldistributed algorithmedge-coloringlinear-time algorithmVizing's theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Cites work

• 4-edge-coloring graphs of maximum degree 3 in linear time
• -list vertex coloring in linear time
• A brief history of edge-colorings -- with personal reminiscences
• A constructive proof of the general Lovász local lemma
• A constructive proof of Vizing's theorem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Bipartite Edge Coloring in O(\Delta m) Time
• Borel Vizing's theorem for graphs of subexponential growth
• Deterministic distributed edge-coloring via hypergraph maximal matching
• Deterministic distributed edge-coloring with fewer colors
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Edge-coloring algorithms for bounded degree multigraphs
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Edge-Coloring Partialk-Trees
• Fast algorithms for edge-coloring planar graphs
• Fast and simple (1 + ) -edge-coloring of dense graphs
• Graph edge coloring. Vizing's theorem and Goldberg's conjecture
• Graph theory
• scientific article; zbMATH DE number 3637904 (Why is no real title available?)
• scientific article; zbMATH DE number 6850477 (Why is no real title available?)
• scientific article; zbMATH DE number 6737879 (Why is no real title available?)
• scientific article; zbMATH DE number 7646025 (Why is no real title available?)
• Locality in Distributed Graph Algorithms
• Measurable versions of Vizing's theorem
• Measurable Vizing's theorem
• New approach to nonrepetitive sequences
• New linear-time algorithms for edge-coloring planar graphs
• Nibbling at long cycles: dynamic (and static) edge coloring in optimal time
• On an estimate of the chromatic class of a \(p\)-graph
• On derandomizing local distributed algorithms
• Parallel Symmetry-Breaking in Sparse Graphs
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• The NP-Completeness of Edge-Coloring
• The power of multi-step Vizing chains
• The probabilistic method
• Three short proofs in graph theory
• Towards the locality of Vizing's theorem

Cited in

(2)

• A linear-time algorithm for (1+)-edge-coloring
• Distributed edge coloring in time polylogarithmic in \({\Delta }\)

This page was built for publication: Fast algorithms for Vizing's theorem on bounded degree graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6930173)