Back to Search
Start Over
Coloring graphs of various maximum degree from random lists
- Source :
- Random Structures & Algorithms. 52:54-73
- Publication Year :
- 2017
- Publisher :
- Wiley, 2017.
-
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 $\mathcal{C}$ of size $\sigma= \sigma(n)$. Such a list assignment is called a \emph{random $(k,\mathcal{C})$-list assignment}. In this paper, we are interested in determining the asymptotic probability (as $n \to \infty$) of the existence of a proper coloring $\varphi$ of $G$, such that $\varphi(v) \in L(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 $n \to \infty$ 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} \Delta^{1/k})$ and $\Delta=O\left(n^{\frac{k-1}{k(k^3+ 2k^2 - k +1)}}\right)$, then the probability that $G$ has an $L$-coloring tends to 1 as $n \rightarrow \infty$. If $k\geq 2$ 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$.
- Subjects :
- FOS: Computer and information sciences
Discrete mathematics
Discrete Mathematics (cs.DM)
Applied Mathematics
General Mathematics
010102 general mathematics
0102 computer and information sciences
01 natural sciences
Computer Graphics and Computer-Aided Design
Graph
Vertex (geometry)
Combinatorics
010201 computation theory & mathematics
coloring from random lists
list coloring
random list
FOS: Mathematics
Mathematics - Combinatorics
Sannolikhetsteori och statistik
Combinatorics (math.CO)
0101 mathematics
Probability Theory and Statistics
Software
Computer Science - Discrete Mathematics
Mathematics
List coloring
Subjects
Details
- ISSN :
- 10429832
- Volume :
- 52
- Database :
- OpenAIRE
- Journal :
- Random Structures & Algorithms
- Accession number :
- edsair.doi.dedup.....027e2c0671c59300d37105fc49afea1d