Combinatorics (math.CO)

Abstract: Given positive integers $p \ge k$, and a non-negative integer $d$, we say a graph $G$ is $(k,d,p)$-choosable if for every list assignment $L$ with $|L(v)|\geq k$ for each $v \in V(G)$ and $|\bigcup_{v\in V(G)}L(v)| \leq p$, there exists an $L$-coloring of $G$ such that each monochromatic subgraph has maximum degree at most $d$. In particular, $(k,0,k)$-choosable means $k$-colorable, $(k,0,+\infty)$-choosable means $k$-choosable and $(k,d,+\infty)$-choosable means $d$-defective $k$-choosable. This paper proves that there are 3-colorable planar graphs that are not $1$-defective $3$-choosable, there are 1-defective 3-choosable graphs that are not 4-choosable, and for any positive integers $\ell \geq k \geq 3$, and non-negative integer $d$, there are $(k,d, \ell)$-choosable graphs that are not $(k,d , \ell+1)$-choosable. These results answer questions asked by \v{S}krekovski [Combin. Probab. Comput. 8, 3(1999), 293-299], Wang and Xu [SIAM J. Discrete Math. 27, 4(2013), 2020-2037], and Kang [J. Graph Theory 73, 3(2013), 342-353], respectively. Our construction of $(k,d, \ell)$-choosable but not $(k,d , \ell+1)$-choosable graphs generalizes the construction of Kr\'{a}l' and Sgall in [J. Graph Theory 49, 3(2005), 177-186] for the case $d=0$.

Abstract: Given a subgroup $H$ of a group $(G,+)$, a $(G,H,k,1)$ difference family (DF) is a set $\mathcal F$ of $k$-subsets of $G$ such that $\{f-f':f,f'\in F, f\neq f',F\in \mathcal F\}=G\setminus H$. Let $g\mathbb Z_{gh}$ is the subgroup of order $h$ in $\mathbb Z_{gh}$ generated by $g$. A $(\mathbb Z_{gh},g\mathbb Z_{gh},k,1)$-DF is called cyclic and written as a $(gh,h,k,1)$-CDF. This paper shows that for $h\in\{2,3,6\}$, there exists a $(gh,h,4,1)$-CDF if and only if $gh\equiv h\pmod{12}$, $g\geq 4$ and $(g,h)\not\in\{(9,3),(5,6)\}$. As a corollary, it is shown that a 1-rotational S$(2,4,v)$ exists if and only if $v\equiv4\pmod{12}$ and $v\neq 28$. This solves the long-standing open problem on the existence of a 1-rotational S$(2,4,v)$. As another corollary, we establish the existence of an optimal $(v,4,1)$-optical orthogonal code with $\lfloor(v-1)/12\rfloor$ codewords for any positive integer $v\equiv 1,2,3,4,6\pmod{12}$ and $v\neq 25$. We also give applications of our results to cyclic group divisible designs with block size four and optimal cyclic $3$-ary constant-weight codes with weight four and minimum distance six.