7-Connected Graphs are 4-Ordered

Rose McCarty; Yan Wang; Xingxing Yu

doi:10.1016/j.jctb.2019.07.002

paper

7-Connected Graphs are 4-Ordered

arXiv:1808.05124 · doi:10.1016/j.jctb.2019.07.002

Abstract

A graph $G$ is $k$ -ordered if for any distinct vertices $v_{1}, v_{2}, \dots, v_{k} \in V (G)$ , it has a cycle through $v_{1}, v_{2}, \dots, v_{k}$ in order. Let $f (k)$ denote the minimum integer so that every $f (k)$ -connected graph is $k$ -ordered. The first non-trivial case of determining $f (k)$ is when $k = 4$ , where the previously best known bounds are $7 \leq f (4) \leq 40$ . We prove that in fact $f (4) = 7$ .

21 pages, 1 figure. Revised version