preprint · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016

Randomly Coloring Graphs of Logarithmically Bounded Pathwidth

Cited by 16Open access

Abstract

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.

Cite this paper

APA 7

Guruswami, V. (2016). Randomly Coloring Graphs of Logarithmically Bounded Pathwidth. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics). https://doi.org/10.4230/lipics.approx-random.2018.57

MLA 9

Guruswami, Venkatesan. “Randomly Coloring Graphs of Logarithmically Bounded Pathwidth.” DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), 2016, https://doi.org/10.4230/lipics.approx-random.2018.57.

Chicago

Guruswami, Venkatesan. 2016. “Randomly Coloring Graphs of Logarithmically Bounded Pathwidth.” DROPS (Schloss Dagstuhl – Leibniz Center for Informatics). https://doi.org/10.4230/lipics.approx-random.2018.57.

Harvard

Guruswami, V. (2016) ‘Randomly Coloring Graphs of Logarithmically Bounded Pathwidth’, DROPS (Schloss Dagstuhl – Leibniz Center for Informatics). Available at: https://doi.org/10.4230/lipics.approx-random.2018.57.

BibTeX

@misc{guruswami2016randomly,
  title = {{Randomly Coloring Graphs of Logarithmically Bounded Pathwidth}},
  author = {Guruswami, Venkatesan},
  journal = {DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)},
  year = {2016},
  doi = {10.4230/lipics.approx-random.2018.57}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.