On the 𝜀-ascent chromatic index of complete graphs

Breytenbach, Jean; Mynhardt, Kieka

doi:10.2140/involve.2015.8.295

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

On the $\varepsilon$-ascent chromatic index of complete graphs

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

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

DOI: 10.2140/involve.2015.8.295

Abstract

An edge ordering of a graph $G = (V, E)$ 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 $ε (G)$ 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 $χ_{ε} (K_{n})$ of colours required to edge colour $K_{n}$ , $n \geq 4$ , such that the length of a shortest maximal ascent is equal to $ε (K_{n}) = 3$ . We obtain new upper and lower bounds for $χ_{ε} (K_{n})$ , which enable us to determine $χ_{ε} (K_{n})$ exactly for $n = 7$ and $n \equiv 2 (mod 4)$ and to bound $χ_{ε} (K_{4 m})$ by $4 m \leq χ_{ε} (K_{4 m}) \leq 4 m + 1$ .

Keywords

edge ordering of a graph, increasing path, depression, edge colouring

Mathematical Subject Classification 2010

Primary: 05C15, 05C78, 05C38

Milestones

Received: 22 July 2013

Accepted: 26 October 2013

Published: 3 March 2015

Communicated by Jerrold Griggs

Authors

Jean A. Breytenbach
Computer Science, Department of Mathematical Sciences Stellenbosch University Private Bag X1 Matieland 7602 South Africa

C. M. (Kieka) Mynhardt
Department of Mathematics and Statistics University of Victoria P.O. Box 1700 STN CSC Victoria, BC V8W 2Y2 Canada

Vol. 8, No. 2, 2015