Score: 0
Proper colorings of a graph in linear time using a number of colors linear in the maximum degree of the graph
Published: December 30, 2025 |
arXiv ID: 2512.24522v1
By: Kritika Bhandari, Mark Huber
A new algorithm for exactly sampling from the set of proper colorings of a graph is presented. This is the first such algorithm that has an expected running time that is guaranteed to be linear in the size of a graph with maximum degree \( Δ\) when the number of colors is greater than \( 3.637 Δ+ 1\).
Similar Papers
91%
An algorithmic Vizing's theorem: toward efficient edge-coloring sampling with an optimal number of colors
Data Structures and Algorithms
Makes computer networks use colors more evenly.
20 Jan 2025
0
90%
Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
Data Structures and Algorithms
Colors graph parts faster with new computer tricks.
9 Feb 2025
0
89%
Dynamic Graph Coloring: Sequential, Parallel, and Distributed
Data Structures and Algorithms
Colors network parts quickly after changes.
10 Dec 2025
1