Remarks on Upper and Lower Bounds for Matching Sequencibility of Graphs

Shuya Chiba, Yuji Nakano

In 2008, Alspach [The Wonderful Walecki Construction, Bull. Inst. Combin. Appl. 52 (2008) 7--20] defined the matching sequencibility of a graph $G$ to be the largest integer $k$ such that there exists a linear ordering of its edges so that every $k$ consecutive edges in the linear ordering form a matching of $G$, which is denoted by $\operatorname{ms}(G)$. In this paper, we show that every graph $G$ of size $q$ and maximum degree $\Delta$ satisfies $\frac12\big\lfloor\frac{q}{\Delta+1}\big\rfloor\leq\operatorname{ms}(G)\leq\big\lfloor\frac{q-1}{\Delta-1}\big\rfloor$ by using the edge-coloring of $G$, and we also improve this lower bound for some particular graphs. We further discuss the relationship between the matching sequencibility and a conjecture of Seymour about the existence of the $k$th power of a Hamilton cycle.