The Linear Arboricity of the Schrijver Graph $SG(2k+2,k)$

Bing Xue ; Liancui Zuo

Bulletin of the Malaysian Mathematical Society, Tome 35 (2012) no. 2

Résumé

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$.

Détail

Classification : 05C15.