choosability

Graph Theory » Coloring » Vertex coloring

Choosability of Graph Powers ★★

Author(s): Noel

Question (Noel, 2013) Does there exist a function $f(k)=o(k^2)$ such that for every graph $G$ , $\text{ch}\left(G^2\right)\leq f\left(\chi\left(G^2\right)\right)?$

Keywords: choosability; chromatic number; list coloring; square of a graph

Posted by Jon Noel
updated July 13th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Bounding the on-line choice number in terms of the choice number ★★

Author(s): Zhu

Question Are there graphs for which $\text{ch}^{\text{OL}}-\text{ch}$ is arbitrarily large?

Keywords: choosability; list coloring; on-line choosability

Posted by Jon Noel
updated April 11th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Choice number of complete multipartite graphs with parts of size 4 ★

Author(s):

Question What is the choice number of $K_{4*k}$ for general $k$ ?

Keywords: choosability; complete multipartite graph; list coloring

Posted by Jon Noel
updated April 11th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Choice Number of k-Chromatic Graphs of Bounded Order ★★

Author(s): Noel

Conjecture If $G$ is a $k$ -chromatic graph on at most $mk$ vertices, then $\text{ch}(G)\leq \text{ch}(K_{m*k})$ .

Keywords: choosability; complete multipartite graph; list coloring

Posted by Jon Noel
updated February 2nd, 2013

add new comment

Graph Theory » Coloring » Homomorphisms

Circular choosability of planar graphs ★

Author(s): Mohar

Let $G = (V, E)$ be a graph. If $p$ and $q$ are two integers, a $(p,q)$ -colouring of $G$ is a function $c$ from $V$ to $\{0,\dots,p-1\}$ such that $q \le |c(u)-c(v)| \le p-q$ for each edge $uv\in E$ . Given a list assignment $L$ of $G$ , i.e.~a mapping that assigns to every vertex $v$ a set of non-negative integers, an $L$ -colouring of $G$ is a mapping $c : V \to N$ such that $c(v)\in L(v)$ for every $v\in V$ . A list assignment $L$ is a $t$ - $(p,q)$ -list-assignment if $L(v) \subseteq \{0,\dots,p-1\}$ and $|L(v)| \ge tq$ for each vertex $v \in V$ . Given such a list assignment $L$ , the graph G is $(p,q)$ - $L$ -colourable if there exists a $(p,q)$ - $L$ -colouring $c$ , i.e. $c$ is both a $(p,q)$ -colouring and an $L$ -colouring. For any real number $t \ge 1$ , the graph $G$ is $t$ - $(p,q)$ -choosable if it is $(p,q)$ - $L$ -colourable for every $t$ - $(p,q)$ -list-assignment $L$ . Last, $G$ is circularly $t$ -choosable if it is $t$ - $(p,q)$ -choosable for any $p$ , $q$ . The circular choosability (or circular list chromatic number or circular choice number) of G is $cch(G) := \inf\{t \ge 1 : G \text{ is circularly $t$-choosable}\}.$