Proper colorings of a graph in linear time using a number of colors linear in the maximum degree of the graph

preprint2025arXivOpen access

Abstract

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 3.637 Δ+ 1.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.