Altitude of 4-regular circulants (Q1773848)

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\)).