Volume 35 • Number 2 • 2012   • The Linear Arboricity of the Schrijver Graph $SG(2k+2,k)$ Bing Xue and Liancui Zuo Abstract. The linear arboricity $la(G)$ of a graph $G$ is the minimum number of linear forests which partition the edge set $E(G)$ of $G$. The vertex linear arboricity $vla(G)$ of a graph $G$ is the minimum number of subsets into which the vertex set $V(G)$ can be partitioned so that every subset induces a linear forest. The Schrijver graph $SG(n,k)$ is the graph whose vertex set consists of all $2$-stable $k$-subsets of the set $[n]=\{0,1,\dots,n-1 \}$ and two vertices A and B are adjacent if and only if $A \cap B= \phi$. In this paper, it is proved that $la(SG(2k+2,k))=\lceil (k+2)/2 \rceil$ for $k\geq 3$ and $vla(SG(2k+2,k))=va(SG(2k+2,k))=2$ for $k\geq 2$. 2010 Mathematics Subject Classification: 05C15. Full text: PDF