Colouring powers of cycles from random lists

DOI10.1016/J.EJC.2003.12.002MaRDI QIDQ1883608zbMATH OpenOpenAlexFDO

Authors Michael Krivelevich, Asaf Nachmias

Publication date 13 October 2004

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0512004

zbMATH Keywords

chromatic numbercolouringcyclerandom lists

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: Let $C_n^k$ be the $k$-th power of a cycle on $n$ vertices (i.e. the vertices of $C_n^k$ are those of the $n$-cycle, and two vertices are connected by an edge if their distance along the cycle is at most $k$). For each vertex draw uniformly at random a subset of size $c$ from a base set $S$ of size $s=s(n)$. In this paper we solve the problem of determining the asymptotic probability of the existence of a proper colouring from the lists for all fixed values of $c,k$, and growing $n$.

Recommendations

• Coloring graphs from random lists of fixed size
• Coloring graphs from random lists of size 2
• Coloring graphs of various maximum degree from random lists
• Coloring complete bipartite graphs from random lists
• Coloring complete and complete bipartite graphs from random lists

Cites work

• Choosability of powers of circuits
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(11)

• Independence polynomials of circulants with an application to music
• Coloring complete and complete bipartite graphs from random lists
• Coloring graphs of various maximum degree from random lists
• Biclique-colouring verification complexity and biclique-colouring power graphs
• Vertex coloring complete multipartite graphs from random lists of size 2
• Coloring graphs from random lists of fixed size
• Colouring clique-hypergraphs of circulant graphs
• Coloring graphs from random lists of size 2
• Coloring hypergraphs from random lists
• DP-coloring of graphs from random covers
• Coloring graphs from random lists

This page was built for publication: Colouring powers of cycles from random lists

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1883608)