#### Vol. 8, No. 2, 2015

 Recent Issues
 The Journal About the Journal Subscriptions Editorial Board Editors’ Addresses Editors’ Interests Scientific Advantages Submission Guidelines Submission Form Ethics Statement Editorial Login Author Index Coming Soon Contacts ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print)
On the $\varepsilon$-ascent chromatic index of complete graphs

### Jean A. Breytenbach and C. M. (Kieka) Mynhardt

Vol. 8 (2015), No. 2, 295–305
##### Abstract

An edge ordering of a graph $G=\left(V,E\right)$ is an injection $f:E\to {ℤ}^{+}$, where ${ℤ}^{+}$ is the set of positive integers. A path in $G$ for which the edge ordering $f$ increases along its edge sequence is called an $f$-ascent; an $f$-ascent is maximal if it is not contained in a longer $f$-ascent. The depression $\epsilon \left(G\right)$ of $G$ is the smallest integer $k$ such that any edge ordering $f$ has a maximal $f$-ascent of length at most $k$. Applying the concept of ascents to edge colourings rather than edge orderings, we consider the problem of determining the minimum number ${\chi }_{\epsilon }\left({K}_{n}\right)$ of colours required to edge colour ${K}_{n}$, $n\ge 4$, such that the length of a shortest maximal ascent is equal to $\epsilon \left({K}_{n}\right)=3$. We obtain new upper and lower bounds for ${\chi }_{\epsilon }\left({K}_{n}\right)$, which enable us to determine ${\chi }_{\epsilon }\left({K}_{n}\right)$ exactly for $n=7$ and $n\equiv 2\phantom{\rule{0.3em}{0ex}}\left(mod\phantom{\rule{0.3em}{0ex}}4\right)$ and to bound ${\chi }_{\epsilon }\left({K}_{4m}\right)$ by $4m\le {\chi }_{\epsilon }\left({K}_{4m}\right)\le 4m+1$.

##### Keywords
edge ordering of a graph, increasing path, depression, edge colouring
##### Mathematical Subject Classification 2010
Primary: 05C15, 05C78, 05C38