Search

A coloring $c$ of the vertices of a graph $G$ is nonrepetitive if there exists no path $v_1v_2\ldots v_{2l}$ for which $c(v_i)=c(v_{l+i})$ for all $1\le i\le l$. Given graphs $G$ and $H$ with $|V(H)|=k$, the lexicographic product $G[H]$ is the graph obtained by substituting every vertex of $G$ by a copy of $H$, and every edge of $G$ by a copy of $K_{k,k}$. %Our main results are the following. We prove that for a sufficiently long path $P$, a nonrepetitive coloring of $P[K_k]$ needs at least $3k+\lfloor k/2\rfloor$ colors. If $k>2$ then we need exactly $2k+1$ colors to nonrepetitively color $P[E_k]$, where $E_k$ is the empty graph on $k$ vertices. If we further require that every copy of $E_k$ be rainbow-colored and the path $P$ is sufficiently long, then the smallest number of colors needed for $P[E_k]$ is at least $3k+1$ and at most $3k+\lceil k/2\rceil$. Finally, we define fractional nonrepetitive colorings of graphs and consider the connections between this notion and the above results.

The on-line choice number of a graph is a variation of the choice number defined through a two person game. It is at least as large as the choice number for all graphs and is strictly larger for some graphs. In particular, there are graphs $G$ with $|V(G)| = 2 \chi(G)+1$ whose on-line choice numbers are larger than their chromatic numbers, in contrast to a recently confirmed conjecture of Ohba that every graph $G$ with $|V(G)| \le 2 \chi(G)+1$ has its choice number equal its chromatic number. Nevertheless, an on-line version of Ohba conjecture was proposed in [P. Huang, T. Wong and X. Zhu, Application of polynomial method to on-line colouring of graphs, European J. Combin., 2011]: Every graph $G$ with $|V(G)| \le 2 \chi(G)$ has its on-line choice number equal its chromatic number. This paper confirms the on-line version of Ohba conjecture for graphs $G$ with independence number at most 3. We also study list colouring of complete multipartite graphs $K_{3\star k}$ with all parts of size 3. We prove that the on-line choice number of $K_{3 \star k}$ is at most $3/2k$, and present an alternate proof of Kierstead's result that its choice number is $\lceil (4k-1)/3 \rceil$. For general graphs $G$, we prove that if $|V(G)| \le \chi(G)+\sqrt{\chi(G)}$ then its on-line choice number equals chromatic number., Comment: new abstract and introduction

The arboricity of a graph G is the minimum number of colours needed to colour the edges of G so that every cycle gets at least two colours. Given a positive integer p, we define the generalized p-arboricity Arb_p(G) of a graph G as the minimum number of colours needed to colour the edges of a multigraph G in such a way that every cycle C gets at least min(|C|; p + 1) colours. In the particular case where G has girth at least p + 1, Arb_p(G) is the minimum size of a partition of the edge set of G such that the union of any p parts induce a forest. If we require further that the edge colouring be proper, i.e., adjacent edges receive distinct colours, then the minimum number of colours needed is the generalized p-acyclic edge chromatic number of G. In this paper, we relate the generalized p-acyclic edge chromatic numbers and the generalized p-arboricities of a graph G to the density of the multigraphs having a shallow subdivision as a subgraph of G.

This paper proves that if $G$ is a graph (parallel edges allowed) of maximum degree 3, then $\chi_c'(G) \leq 11/3$ provided that $G$ does not contain $H_1$ or $H_2$ as a subgraph, where $H_1$ and $H_2$ are obtained by subdividing one edge of $K_2^3$ (the graph with three parallel edges between two vertices) and $K_4$, respectively. As $\chi_c'(H_1) = \chi_c'(H_2) = 4$, our result implies that there is no graph $G$ with $11/3 < \chi_c'(G) < 4$. It also implies that if $G$ is a 2-edge connected cubic graph, then $\chi'(G) \le 11/3$.