文章基本信息

标题：Randomly Coloring Graphs of Logarithmically Bounded Pathwidth
本地全文：下载
作者：Shai Vardi
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：116
页码：1-19
DOI：10.4230/LIPIcs.APPROX-RANDOM.2018.57
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Random coloring; Glauber dynamics; Markov-chain Monte Carlo