Arboricity-dependent algorithms for edge coloring

DOI10.4230/LIPICS.SWAT.2024.12MaRDI QIDQ6891144zbMATH OpenFDO

Authors Sayan Bhattacharya, M. Costa, Nadav Panski, Shay Solomon

Publication date 2 December 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SWAT.2024.12

zbMATH Keywords

arboricitydynamic algorithmsedge coloringgraph algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Arboricity and Subgraph Listing Algorithms
• Deterministic distributed \((\Delta + o(\Delta))\)-edge-coloring, and vertex-coloring of graphs with bounded diversity
• Dynamic Edge Coloring with Improved Approximation
• scientific article; zbMATH DE number 6850309 (Why is no real title available?)
• scientific article; zbMATH DE number 6850477 (Why is no real title available?)
• Nibbling at long cycles: dynamic (and static) edge coloring in optimal time
• On an estimate of the chromatic class of a \(p\)-graph
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• The power of multi-step Vizing chains

Cited in

(3)

• Edge-coloring sparse graphs with Colors in quasilinear time
• Faster edge coloring by partition sieving
• Vizing's theorem in near-linear time

This page was built for publication: Arboricity-dependent algorithms for edge coloring

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