Clark, T. C.; Falvai, B.; Hendersonand, D. R.; Mynhardt, C. M. Altitude of 4-regular circulants. (English) Zbl 1073.05061 AKCE Int. J. Graphs Comb. 1, No. 2, 149-166 (2004). The altitude \(\alpha (G)\) of a graph \(G\) is the largest integer \(k\) such that for each linear ordering \(f\) of its edges, \(G\) has a (simple) path of length \(k\), for which \(f\) increases along its edge sequence. The altitude of \(G\) is bounded above by its chromatic index \(\chi '(G)\). The height of an edge coloring is the maximal length of a simple path with strictly increasing edge colors. Here a order on the colors is fixed. The first result of the paper under review states that if a \(4\)-regular graph with girth \(4\) has an edge coloring with \(4\) colors and height \(3\), it is bipartite. This result is used to investigate the altitude of \(4\)-regular circulant graphs \(C_n \langle a,b \rangle\), i.e., the graph with set of vertices \(\{0, \dots , n-1\}\) where vertices \(i\) and \(j\) are adjacent if and only if \(i-j\) is congruent to \(\pm a\) or \(\pm b\) modulo \(n\).The following results are obtained. If \(n\) is even and \(C_n \langle a,b \rangle\) is connected and triangle-free, then it has altitude \(3\) if and only if it is bipartite, otherwise it has altitude \(4\). Note that a characterization of bipartite circulants has been given by the reviewer [Discrete Math. 268, 153–169 (2003; Zbl 1028.05024)]. If \(n\) is odd, \(C_n \langle a,b \rangle\) is connected and triangle-free, then \(4 \leq \alpha (C_n \langle a,b \rangle ) \leq 5.\) For circulants containing triangles, the following partial results are obtained: If \(n \geq 6\) is even, then \( \alpha (C_n \langle 1,2 \rangle) = 3\). If \(n \geq 7\) is odd, then \(3 \leq \alpha (C_n \langle 1,2 \rangle) \leq 4.\) Removing any edge from \(C_n \langle 1,2 \rangle\) leads to altitude \(3\), if \(n \equiv 1\) (mod \(4\)). Reviewer: Clemens Heuberger (Graz) Cited in 1 Document MSC: 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 05C15 Coloring of graphs and hypergraphs 05C38 Paths and cycles Keywords:edge ordering, circulant graphs, edge colorings Citations:Zbl 1028.05024 PDFBibTeX XMLCite \textit{T. C. Clark} et al., AKCE Int. J. Graphs Comb. 1, No. 2, 149--166 (2004; Zbl 1073.05061)