Abstract. Assume [Formula: see text] is a partition of [Formula: see text]. A [Formula: see text]-list assignment of [Formula: see text] is a [Formula: see text]-list assignment [Formula: see text] of [Formula: see text] such that the color set [Formula: see text] can be partitioned into [Formula: see text] sets [Formula: see text] such that for each [Formula: see text] and each vertex [Formula: see text] of [Formula: see text], [Formula: see text]. We say [Formula: see text] is [Formula: see text] -choosable if [Formula: see text] is [Formula: see text]-colorable for any [Formula: see text]-list assignment [Formula: see text] of [Formula: see text]. The concept of [Formula: see text]-choosability is a refinement of choosability that puts [Formula: see text]-choosability and [Formula: see text]-colorability in the same framework. If [Formula: see text] is close to [Formula: see text], then [Formula: see text]-choosability is close to [Formula: see text]-colorability; if [Formula: see text] is close to 1, then [Formula: see text]-choosability is close to [Formula: see text]-choosability. This paper studies Hadwiger’s conjecture in the context of [Formula: see text]-choosability. Hadwiger’s conjecture is equivalent to saying that every [Formula: see text]-minor-free graph is [Formula: see text]-choosable for any positive integer [Formula: see text], where [Formula: see text] is the multiset consisting of [Formula: see text] copies of 1. We prove that for [Formula: see text], for any partition [Formula: see text] of [Formula: see text] other than [Formula: see text], there is a [Formula: see text]-minor-free graph [Formula: see text] that is not [Formula: see text]-choosable. We then construct several types of [Formula: see text]-minor-free graphs that are not [Formula: see text]-choosable, where [Formula: see text] gets larger as [Formula: see text] gets larger. In particular, for any [Formula: see text] and any [Formula: see text], there exists [Formula: see text] such that for any [Formula: see text], for any partition [Formula: see text] of [Formula: see text] with [Formula: see text], there is a [Formula: see text]-minor-free graph that is not [Formula: see text]-choosable. The [Formula: see text] case of this result was recently proved by Steiner, and our proof uses a similar argument. We also generalise this result to [Formula: see text]-list coloring.

This paper studies the strong fractional choice number $ch^s_f(G)$ and the strong fractional paint number $pt^s_f(G)$ of a graph $G$. We prove that these parameters of any finite graph are rational numbers. On the other hand, for any positive integers $p,q$ satisfying $2 \le \frac{2p}{2q+1} \leq \lfloor\frac{p}{q}\rfloor$, we construct a graph $G$ with $ch^s_f(G) = pt^s_f(G) = \frac{p}{q}$. The relationship between $pt^s_f(G)$ and $ch^s_f(G)$ is explored. We prove that the gap $pt^s_f(G)-ch^s_f(G)$ can be arbitrarily large. The strong fractional choice number of a family $\mathcal{G}$ of graphs is the supremum of the strong fractional choice numbers of graphs in $\mathcal{G}$. Let $\mathcal{P}$ denote the class of planar graphs and $\mathcal{P}_{k_1,\ldots, k_q}$ denote the class of planar graphs without $k_i$-cycles for $i=1,\ldots, q$. We prove that $3 + \frac{1}{2} \leq ch^s_f(\mathcal{P}_{ 4}) \leq 4$, $ch^s_f(\mathcal{P}_{ k})=4$ for $k \in \{5,6\}$, $3 +\frac{1}{12} \leq ch^s_f(\mathcal{P}_{ 4,5}) \leq 4$, and $ch^s_f(\mathcal{P}) \ge 4+\frac 13$. The last result improves the lower bound $4+\frac 29$ in [Zhu, J. Combin. Theory Ser. B, 122 (2017), pp. 794--799].

We prove that it is always possible to color online nonrepetitively any (partial) k-tree (that is, graphs with tree-width at most k) with 4k colors. This implies that it is always possible to color online nonrepetitively cycles, trees and series-parallel graphs with 16 colors. Our results generalize the respective (offline) nonrepetitive coloring results.

A total-weighting of a graph $G=(V,E)$ is a mapping $f$ which assigns to each element $y\in V\cup E$ a real number $f(y)$ as the weight of $y$. A total-weighting $f$ of $G$ is proper if the coloring $\phi_{f}$ of the vertices of $G$ defined as $\phi_{f}(v)=f(v)+\sum_{e\in E(v)}f(e)$ is a proper coloring of $G$, i.e., $\phi_{f}(v)\ne\phi_{f}(u)$ for any edge $uv$, where $E(v)$ is the set of edges of $G$ incident to $v$. For positive integers $k$ and $k'$, a graph $G$ is called $(k,k')$-total-weight-choosable if whenever each vertex $v$ is given $k$ permissible weights and each edge $e$ is given $k'$ permissible weights, there is a proper total-weighting $f$ of $G$ which uses only permissible weights on each element $y\in V\cup E$. It is known that every tree is (2,2)-total-weight-choosable and every tree other than $K_2$ is (1,3)-total-weight-choosable. However, the problem of determining which trees are (1,2)-total-weight-choosable remained open. This paper solves this problem and characterizes all (1,2)-total-weight-choosable trees. Based on this characterization, we give an algorithm that determines in linear time whether a given tree is (1,2)-total-weight-choosable.

Energy efficiency is an important issue in the study of wireless sensor networks. Given a set of targets and a set of sensors with bounded lifetime, the maximum lifetime k-coverage problem is to schedule active/sleeping status of sensors to maximize the time period during which every target is covered by at least k active sensors. Previously, it was known that when the sensing ranges are uniform, this problem has a polynomial time (4+ε)-approximation for k = 1 and (6+ε)-approximation for k = 2. In this paper, we make significant progress by showing that for any positive integer k, there exists a polynomial-time (3 + ε)-approximation.

A k-fold coloring of a graph assigns to each vertex a set of k colors, and color sets assigned to adjacent vertices are disjoint. The kth chromatic number $\chi_k(G)$ of a graph G is the minimum total number of colors needed in a k-fold coloring of G. Given a graph $G=(V,E)$ and an integer $m\geq0$, the m-cone of G, denoted by $\mu_m(G)$, has vertex set $(V\times\{0,1,\dots,m\})\cup\{u\}$ in which u is adjacent to every vertex of $V\times\{m\}$, and $(x,i)(y,j)$ is an edge if $xy\in E$ and $i=j=0$ or $xy\in E$ and $|i-j|=1$. This paper studies the kth chromatic number of the cone graphs. An upper bound for $\chi_k(\mu_m(G))$ in terms of $\chi_k(G)$, k, and m are given. In particular, it is proved that for any graph G, if $m\geq2k$, then $\chi_k(\mu_m(G))\leq\chi_k(G)+1$. We also find a surprising connection between the kth chromatic number of the cone graph of G and the circular chromatic number of G. It is proved that if $\chi_k(G)/k>\chi_c(G)$ and $\chi_k(G)$ is even, then for sufficiently large m, $\chi_k(\mu_m(G))=\chi_k(G)$. In particular, if $\chi(G)>\chi_c(G)$ and $\chi(G)$ is even, then for sufficiently large m, $\chi(\mu_m(G))=\chi(G)$.

This paper studies the fractional chromatic number of graphs with maximum degree at most 3. It is proved that if G is triangle free and has maximum degree at most 3, then $\chi_f(G)\leq3-\frac{3}{64}$. If G has girth at least k and maximum degree at most 3, then $\chi_f(G)\leq c_k$, where $c_k$ is a decreasing sequence converging to $8/3$, and $c_{15}\approx2.66681$.

The two-coloring number of graphs, which was originally introduced in the study of the game chromatic number, also gives an upper bound on the degenerate chromatic number as introduced by Borodin. It is proved that the two-coloring number of any planar graph is at most nine. As a consequence, the degenerate list chromatic number of any planar graph is at most nine. It is also shown that the degenerate diagonal chromatic number is at most 11 and the degenerate diagonal list chromatic number is at most 12 for all planar graphs.

We introduce and study adapted list coloring of graphs and hypergraphs. This is a generalization of ordinary list coloring and adapted coloring, and has more applications than these. We prove that the upper bounds on the adaptable choosability of graphs and uniform hypergraphs in terms of maximum degree are sufficiently stronger than those on the ordinary choosability, while the bounds in terms of degeneracy are the same. We also characterize simple graphs with adaptable choosability 2.

Let G be a graph. A circular distance two labeling with span k is a function $f: V(G) \to \{0, 1, 2, \ldots, k-1\}$ such that (1) $2 \leq |f(u)-f(v)| \leq k-2$ if u and v are adjacent and (2) $f(u) \neq f(v)$ if u and v are of distance two apart. We denote by $\lambda_c(G)$ the smallest span of a circular distance two labeling for G. Let $\Delta(G)$ be the maximum degree of G. We prove, for any outerplanar graph G with $\Delta(G) \geq 15$, $\lambda_c(G)=\Delta(G) +3$. It is also shown that there exist outerplanar graphs G with $\Delta(G) = 2, 3, 4, 5$ for which $\lambda_c(G) = \Delta(G) +4$. Moreover, we prove that $\lambda_c(G) \leq \Delta(G) +5$ for any triangulated outerplanar graph, $\lambda_c(G) \leq \Delta(G) +7$ for any outerplanar graph, and $\lambda_c(G) \leq \Delta(G) +4$ for any outerplanar graph with $\Delta(G) \geq 11$. Immediate consequences of our results include that $\lambda(G) \leq \Delta(G) + 2$ for any outerplanar graphs with $\Delta(G) \geq 15$, where $\lambda(G)$ is the minimum k of a k-L(2, 1)-labeling (or distance two labeling) for G.

For a graph G, let $\diam(G)$ denote the diameter of G. For any two vertices u and v in G, let $d(u, v)$ denote the distance between u and v. A multilevel distance labeling (or distance labeling) for G is a function f that assigns to each vertex of G a nonnegative integer such that for any vertices u and v, $|f(u)-f(v)| \geq \diam(G) - d_G(u, v) +1$. The span of f is the largest number in $f(V)$. The radio number of G, denoted by $rn(G)$, is the minimum span of a distance labeling for G. In this paper, we completely determine the radio numbers for paths and cycles.

In the 1-rate(f) network, each link can carry up to f messages for some integer f. The classical model is the special case when f=1. We show that a network is strictly nonblocking under the 1-rate(f) model if and only if it is strictly nonblocking under the classical model.

A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number (also known as the star chromatic number). We prove that members of a certain family of circulant graphs are star extremal. The result generalizes some known theorems of Sidorenko [Discrete Math., 91 (1991), pp. 215--217] and Gao and Zhu [Discrete Math., 152 (1996), pp. 147--156]. We show relations between circulant graphs and distance graphs and discuss their star extremality. Furthermore, we give counterexamples to two conjectures of Collins [SIAM J. Discrete Math., 11 (1998), pp. 330--339] on asymptotic independence ratios of circulant graphs.

Consider the problem of transporting a set of objects between the vertices of a simple graph by a vehicle that traverses the edges of the graph. The problem of finding a shortest tour for the vehicle to transport all objects from their initial vertices to their destination vertices is called the vehicle routing problem. The problem is multiple capacity if the vehicle can handle more than one objects at a time. The problem is preemptive if objects can be unloaded at the intermediate vertices. In this paper, we present an O(kn+n2) time algorithm for multiple capacity preemptive vehicle routing problem on paths, where k is the number of objects to be moved and n is the number of vertices in the path.

We discuss the existence of homomorphisms of arbitrary digraphs to a fixed oriented cycle C. Our main result asserts that if the cycle C is unbalanced then a digraph G is homomorphic to. C if and only if (1) every oriented path homomorphic to G is also homomorphic to C, and (2) the length of every cycle of G is a multiple of the length of C. This answers a conjecture from an earlier paper with H. Zhou and generalizes a result proved there. We also show that this characterization does not hold for balanced cycles. We relate these results to work on the complexity of homomorphism problems.