2026-08-16T23:22:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9461 2024-03-06T10:44:27Z ddc:004 open_access

Randomly Coloring Graphs of Logarithmically Bounded Pathwidth Vardi, Shai Random coloring Glauber dynamics Markov-chain Monte Carlo We consider the problem of sampling a proper k-coloring of a graph of maximal degree Delta uniformly at random. We describe a new Markov chain for sampling colorings, and show that it mixes rapidly on graphs of logarithmically bounded pathwidth if k >=(1+epsilon)Delta, for any epsilon>0, using a hybrid paths argument. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shai Vardi 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.57 urn:nbn:de:0030-drops-94618 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.57 eng https://creativecommons.org/licenses/by/3.0/legalcode