Coloring graphs of various maximum degree from random lists

DOI10.1002/RSA.20725zbMATH Open1386.05054OpenAlexW2583222403MaRDI QIDQ4601441FDOQ4601441

Authors Carl Johan Casselgren

Publication date 16 January 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

list coloringcoloring from random listsrandom list

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

Abstract: Let $G=G(n)$ be a graph on $n$ vertices with maximum degree $Delta=Delta(n)$. Assign to each vertex $v$ of $G$ a list $L(v)$ of colors by choosing each list independently and uniformly at random from all $k$-subsets of a color set $mathcalC$ of size $sigma=sigma(n)$. Such a list assignment is called a emph{random $(k,mathcalC)$-list assignment}. In this paper, we are interested in determining the asymptotic probability (as $noinfty$) of the existence of a proper coloring $varphi$ of $G$, such that $varphi(v)inL(v)$ for every vertex $v$ of $G$, a so-called $L$-coloring. We give various lower bounds on $sigma$, in terms of $n$, $k$ and $Delta$, which ensures that with probability tending to 1 as $noinfty$ there is an $L$-coloring of $G$. In particular, we show, for all fixed $k$ and growing $n$, that if $sigma(n)=omega(n^{1/k^2}Delt{a}^{1/k})$ and $Delta=Oleft(n^{frack-1k(k^3+2k^2-k+1)}ight)$, then the probability that $G$ has an $L$-coloring tends to 1 as $nightarrowinfty$. If $kgeq2$ and $Delta=Omega(n^{1/2})$, then the same conclusion holds provided that $sigma=omega(Delta)$. We also give related results for other bounds on $Delta$, when $k$ is constant or a strictly increasing function of $n$.

Recommendations

• Coloring graphs from random lists of fixed size
• Coloring graphs from random lists of size 2
• Coloring complete and complete bipartite graphs from random lists
• Coloring complete bipartite graphs from random lists
• Colouring powers of cycles from random lists

Cited in

(10)

• Coloring hypergraphs from random lists
• On-line list colouring of random graphs
• Coloring complete and complete bipartite graphs from random lists
• Coloring graphs from random lists of fixed size
• Coloring complete bipartite graphs from random lists
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Coloring graphs from random lists of size 2
• Colouring powers of cycles from random lists
• Maximizing the chances of a color match
• Vertex coloring complete multipartite graphs from random lists of size 2

This page was built for publication: Coloring graphs of various maximum degree from random lists

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