A note on the list vertex arboricity of toroidal graphs

The vertex arboricity $a\left(G\right)$ of a graph $G$ is the minimum number of colors required to color the vertices of $G$ such that no cycle is monochromatic. The list vertex arboricity $a_l\left(G\right)$ is the list-coloring version of this concept. In this note, we prove that if $G$ is a toroidal graph, then $a_l\left(G\right)\le 4$; and $a_l\left(G\right)=4$ if and only if $G$ contains $K_7$ as an induced subgraph.     

Proper connection and size of graphs

An edge-coloured graph $G$ is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph $G,$ denoted by $\mathrm{pc}\left(G\right)$, is the smallest number of colours that are needed in order to make $G$ properly connected. Our main result is the following: Let $G$ be a connected graph of order $n$ and $k\ge 2$. If $\left|E\left(G\right)\right|\ge \left(\genfrac{}{}{0ex}{}{n?k?1}{2}\right)+k+2$, then $\mathrm{pc}\left(G\right)\le k$ except when $k=2$ and $G\in \{G_1,G_2\},$ where $G_1=K_1\vee (2K_1+K_2)$ and $G_2=K_1\vee (K_1+2K_2).$     

Extremal product-one free sequences in Dihedral and Dicyclic Groups

Let $G$ be a finite group, written multiplicatively. The Davenport constant of $G$ is the smallest positive integer $D\left(G\right)$ such that every sequence of $G$ with $D\left(G\right)$ elements has a non-empty subsequence with product $1$. Let $D_{2n}$ be the Dihedral Group of order $2n$ and $Q_{4n}$ be the Dicyclic Group of order $4n$. Zhuang and Gao (2005) showed that $D\left(D_{2n}\right)=n+1$ and Bass (2007) showed that $D\left(Q_{4n}\right)=2n+1$. In this paper, we give explicit characterizations of all sequences $S$ of $G$ such that $\left|S\right|=D\left(G\right)?1$ and $S$ is free of subsequences whose product is 1, where $G$ is equal to $D_{2n}$ or $Q_{4n}$ for some $n$.     

Maximum average degree and relaxed coloring

We say a graph is $(d,d,\dots ,d,0,\dots ,0)$-colorable with $a$ of $d$’s and $b$ of $0$’s if $V\left(G\right)$ may be partitioned into $b$ independent sets $O_1,O_2,\dots ,O_b$ and $a$ sets $D_1,D_2,\dots ,D_a$ whose induced graphs have maximum degree at most $d$. The maximum average degree, $mad\left(G\right)$, of a graph $G$ is the maximum average degree over all subgraphs of $G$. In this note, for nonnegative integers $a,b$, we show that if $mad\left(G\right)<\frac{4}{3}a+b$, then $G$ is $(1_1,1_2,\dots ,1_a,0_1,\dots ,0_b)$-colorable.     

Some multicolor bipartite Ramsey numbers involving cycles and a small number of colors

For bipartite graphs $G_1,G_2,\dots ,G_k$, the bipartite Ramsey number $b(G_1,G_2,\dots ,G_k)$ is the least positive integer $b$ so that any coloring of the edges of $K_{b,b}$ with $k$ colors will result in a copy of $G_i$ in the $i$th color for some $i$. In this paper, our main focus will be to bound the following numbers: $b(C_{2t_1},C_{2t_2})$ and $b(C_{2t_1},C_{2t_2},C_{2t_3})$ for all $t_i\ge 3,$$b(C_{2t_1},C_{2t_2},C_{2t_3},C_{2t_4})$ for $3\le t_i\le 9,$ and $b(C_{2t_1},C_{2t_2},C_{2t_3},C_{2t_4},C_{2t_5})$ for $3\le t_i\le 5.$ Furthermore, we will also show that these mentioned bounds are generally better than the bounds obtained by using the best known Zarankiewicz-type result.     

On (Kq,k) vertex stable graphs with minimum size

A graph $G$ is a $(K_q,k)$ vertex stable graph if it contains a $K_q$ after deleting any subset of $k$ vertices. We give a characterization of $(K_q,k)$ vertex stable graphs with minimum size for $q=3,4,5$.