{"ID":2824151,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.24522","arxiv_id":"2512.24522","title":"Proper colorings of a graph in linear time using a number of colors linear in the maximum degree of the graph","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\\).","short_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\\).","url_abs":"https://arxiv.org/abs/2512.24522","url_pdf":"https://arxiv.org/pdf/2512.24522v1","authors":"[\"Kritika Bhandari\",\"Mark Huber\"]","published":"2025-12-30T23:51:07Z","proceeding":"math.PR","tasks":"[\"math.PR\",\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}