Coloring graphs of various maximum degree from random lists

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

Authors: Carl Johan Casselgren 

Publication date: 16 January 2018

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

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$.

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

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

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)

Cited In (10)

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

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)