ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 13 (2017) 427-460 Properties, proved and conjectured, of Keller, Mycielski, and queen graphs Wendy Myrvold University of Victoria, Victoria, British Columbia, Canada Peter Saltzman Berkeley, California, USA Stan Wagon Macalester College, St. Paul, Minnesota, USA Received 28 June 2016, accepted 30 April 2017, published online 26 May 2017 We prove several results about three families of graphs. For queen graphs, defined from the usual moves of a chess queen, we find the edge-chromatic number in almost all cases. In the unproved case, we have a conjecture supported by a vast amount of computation, which involved the development of a new edge-coloring algorithm. The conjecture is that the edge-chromatic number is the maximum degree, except when simple arithmetic forces the edge-chromatic number to be one greater than the maximum degree. For Mycielski graphs, we strengthen an old result that the graphs are Hamiltonian by showing that they are Hamilton-connected (except M3, which is a cycle). For Keller graphs Gd, we establish, in all cases, the exact value of the chromatic number, the edge-chromatic number, and the independence number; and we get the clique covering number in all cases except 5 < d < 7. We also investigate Hamiltonian decompositions of Keller graphs, obtaining them up to G6. Keywords: Edge coloring, Keller graphs, Mycielski graphs, queen graphs, Hamiltonian, class one. Math. Subj. Class.: 05C15, 05C45 E-mail addresses: witek@beit.tech (Witold Jarnicki), wendym@cs.uvic.ca (Wendy Myrvold), saltzman.pwa@gmail.com (Peter Saltzman), wagon@macalester.edu (Stan Wagon) Witold Jarnicki Beit.tech, Kraków, Poland Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 427 Ars Math. Contemp. 13 (2017) 275-291 1 Introduction Inspired by computational experiments, we prove several results about some families of graphs. We show in §5 that all Mycielski graphs (except the 5-cycle M3) are Hamilton-connected. In §6, we establish the size of a maximum independent set for all Keller graphs and investigate some other parameters, determining the chromatic number of both the graphs and their complements, and also the edge-chromatic number. In particular, we prove that the edge-chromatic number of each Keller graph equals its degree. We also find the clique covering number for all cases except dimension 5, 6, and 7. And in §2—§4 we present a detailed study of queen graphs, resolving the edge-chromatic number in most cases. Recall that the problem of coloring the edges of a graph is much simpler than the classic vertex-coloring problem. There are only two possibilities for the edge-chromatic number because of Vizing's classic theorem [2, §6.2] that the edge-chromatic number x'(G) is either A(G) or A(G) + 1, where A(G) is the maximum vertex degree; the first case is called class 1; the second, class 2. Let ne(G) denote the number of edges, nv the number of vertices, and p(G) the number of edges in a maximum matching. Some graphs have too many edges to be class 1. An overfull graph G is one for which ne(G) > A(G) v (G) 2 For such a graph, A(G)p(G) < ne(G), and this inequality implies that G must be class 2; so any overfull graph is class 2. The reason for this is that each color class is a matching and so has size at most p(G); if class 1, the number of colored edges would be at most A(G)p(G) which is too small to capture all edges. In §2, we present results and an intriguing conjecture related to edge coloring of the standard queen graph Qm,n: the conjecture is that Qm,n is class 1 whenever it is not overfull. Computation and proofs yield the truth of this conjecture for m < 10 and all values of n > m; the exact conjecture is that the queen is class 1 for n < 1 (2m2 — 11m + 12). In Theorem 4.1, we prove this for n < 1 (m2 — 3m + 2). For the extensive computations we developed a general edge-coloring algorithm that succeeded in finding class-1 colorings for some queen graphs having over two million edges. Our notation is fairly standard: Kn is the complete graph on n vertices; Cn is an n-cycle; x(G) is the chromatic number; Xfrac(G) is the fractional chromatic number; a(G) is the size of a largest independent set; w(G) is the size of a largest clique; 0(G) is the clique covering number (same as x(Gc)). Occasionally G will be omitted from these functions where the context is clear. A vertex of G is called major if its degree equals A(G). Graphs are always simple graphs, with the exception of some queen graph discussions, where multigraphs appear. A Hamiltonian path (resp. cycle) is a path (resp. cycle) that passes through all vertices and does not intersect itself. A graph is Hamiltonian if there is a Hamiltonian cycle; a graph is Hamilton-connected (HC) if, for any pair u, v of vertices, there is a Hamiltonian path from the u to v. We will make use of Fournier's Theorem [9, 10] that a graph is class 1 if the subgraph induced by the vertices of maximum degree is a forest. This theorem is a straightforward consequence of Vizing's adjacency lemma [20, pp. 24, 54, 55]. We thank Joan Hutchinson for a careful reading and helpful suggestions, David Pike for the interesting comment about edge-coloring pioneer F. Walecki, and a referee for some valuable comments. n W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 2 Rook and bishop graphs The family of (not necessarily square) queen graphs presents a number of well-known combinatorial challenges. In this and the following two sections, we study the Vizing classification of queen graphs, a problem that turns out to have unexpected complexity. Queens on a chessboard can make all the moves of rooks and bishops, and thus queen graphs are the union of the rook graph and (white and black) bishop graphs. We therefore start, in this section, by looking at rook and bishop graphs separately. Then in §§3 and 4, we will show how these rook and bishop results lead to a variety of class-1 queen colorings. It is well known that rook graphs behave similarly to their one-dimensional cousins, the complete graphs: they are class 2 if and only if both dimensions are odd. Perhaps more surprising, all bishop graphs are class 1. These two results already suffice to show that queen graphs are class 1 when at least one of the dimensions is even: just take the union of a class 1 rook coloring and a class 1 bishop coloring. When both dimensions are odd, however, the classification of queen graphs becomes much harder. A straightforward counting argument shows that such odd queen graphs are eventually class 2: for m and n odd, Qm,n is class 2 if n > 1 (2m3 - 11m + 18). On the other hand, we prove below (Theorem 4.1) that for m and n odd, Qm,n is class 1 if m < n < 1 (m2 - 3m + 2). As we will also show, the method we use cannot produce class-1 colorings all the way up to the cubic limit, and thus we leave essentially open the problem of determining whether there are any class-2 queen graphs when 1 (m2 - 3m + 4) < n < 1 (2m3 - 11m + 12). We do, however, describe an algorithmic approach that gives lots of data to support the conjecture that there are no such graphs. Recall that bishops move diagonally on a chessboard and rooks (Fig. 1) move horizontally or vertically. Because a queen can move diagonally, horizontally, or vertically, Qm,n, the graph of queen moves, is the union of its two edge subgraphs Bm,n and Rm,n, where Bm,n denotes the graph of bishop moves on an m x n board, and Rmn denotes the rook graph; the latter is just the Cartesian product KmQKn. The bishop graph is disconnected: it is the union of graphs corresponding to a white bishop and a black bishop (where we take the lower left square as being white). We will use WBm,n for the white bishop graph. It is natural to try to get edge-coloring results for the queen by combining such results for bishops and rooks, so we review the situation for those two pieces. The classic result on edge-coloring complete graphs is also essential, so we start there. Lucas [13, p. 177] attributes the first part of Proposition 2.1 to Felix Walecki. Proposition 2.1. x'(Kn) is n - 1 when n is even (and so the graph is class 1) and n when n is odd (the graph is class 2). Moreover, when n is odd every coloring has the property that no missing color at a vertex is repeated. Also, for all n, if M is a maximum matching of Kn, then x'(K„ \ M) = n - 1. Proof. For the even case, take the vertices to be v where vi,..., vn_i are the vertices of a regular (n - 1)-gon, and vn is the center. Use color i on vj - vn and on edges perpendicular to this edge. For n odd, one can use a regular n-gon to locate all the vertices and use n colors for the exterior n-cycle; then color any other edge with the same color used for the exterior edge that parallels it. (Alternatively, add a dummy vertex vn+1 and use the even-order result, discarding at the end any edges involving the dummy vertex.) Note that Kn, with n odd, is overfull, so the preceding coloring is optimal. Further, the coloring has the property that the missing colors at the vertices are 1,2,..., n. This phenomenon, that no missing color is repeated, is easily seen to hold for any class-2 coloring of Kn, with n 183 Ars Math. Contemp. 13 (2017) 275-291 odd. Because x'(Kn) = ne(Kn)/p(Kn), each color class in any optimal coloring of Kn is a maximum matching. These graphs are edge transitive, so all maximum matchings are the same, which yields the final assertion of the Proposition. □ Theorem 2.2. The rook graph Rm,n is class 1 except when both dimensions are odd, in which case it is overfull, and so is class 2. Proof. For the class-2 result, we have A = m + n - 2, and ne = m(n) + n(m), which leads to ne - 2 (mn - 1)A = y > 0. For class 1, the even case is trivial by Proposition 2.1, since we can use colors 1 through n - 1 on each row and n through m + n - 2 on each column. For the case of m even and n odd (which suffices by symmetry; see Fig. 1), use colors 1 through n on each complete row, and ensure that color 1 is missing at the vertices in the first column, color 2 is missing on the second column, and so on. The color set consisting of i, n + 1,..., n + m - 2 can be used on the ith column. □ 1 2 3 4 5 on all rows Figure 1: The rook graph R4,5 is class 1. Use colors 1-5 on the rows, with color i missing on the vertices in the ith column. Then use i, 6, and 7 on the ith column. For the class-2 case of the preceding result one can easily give an explicit A+1 coloring, either by the method used in Theorem 3.1 or the ladder method of Proposition 4.3. The bishop situation had not been investigated until the work of Saltzman and Wagon [16, 17, 18], who proved that all bishop graphs are class 1. Theorem 2.3. All bishop graphs Bm,n are class 1. Proof. Assume m < n. We have A(Bm,n) = 2m - 2, except for one case: if m is even, then A(Bm,m) = 2m - 3. The graph can be decomposed into paths as follows. Note that any bishop edge is a diagonal line with a natural "length": the Euclidean distance between the vertices divided by %/2. Let G+ consist of all edges of length 1 having negative slope and paths of length m -1, with edges having positive slope (in Fig. 2 this graph is the set of green and red edges). This subgraph consists of disjoint paths; the edges of each path can be 2-colored. Define G- the same way, but with the slopes reversed. Get the full family by defining G+, G-, G+, G-,..., G+m/2,, G-m/2j, where G± is defined similarly to G±, but using edges of length i and m - i. The proof that these edge subgraphs partition the bishop edges is easy (see [16, 17]). Each of these subgraphs, being a collection of disjoint W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 paths, can be 2-edge colored (for definiteness and because it plays a role in later work, we will always use the first of the two colors on the leftmost edge of each path; and the resulting coloring will be referred to as the canonical bishop edge-coloring). When m is odd the color count is 4m-1 = 2m - 2. When m is even and n > m, the graphs GGm/2 and Gm/2 coincide and the color count is 4( y - 1) + 2 = 2m - 2. But when m is even and n = m, then GGm/2 = Gm/2 and this subgraph consists of only disjoint edges; it is therefore 1-colorable and the color count is 4( m - 1) + 1 = 2m - 3. Note that for odd m, some of the edge subgraphs when restricted to the black bishop will be empty, but that is irrelevant. The black bishop will use fewer colors, but the colors are disjoint from the ones used for the white bishop and it is the latter that determines x'. d o o o o o o o o o o o o o o o o o o o o o o o Figure 2: Top: The red and green edges form the subgraph G+ of WB5 9, the white bishop graph; blue and yellow form G-. Bottom: The purple and green edges form G+; cyan and pink are G-. The total color count is 8, the maximum degree of the graph. An interesting and useful type of coloring is one in which one color is as rare as can be. The next lemma shows that, for Bn,n with n odd, the canonical coloring is such that the rarest color occurs the smallest possible number of times: once. Lemma 2.4. In the canonical coloring of Bn n, n odd, the rarest color occurs on one edge only. Proof. Referring to the subgraphs of Theorem 2.3's proof, all the paths in the black bishop part of G-n_1)/2 are isolated edges, and the same is true for the white bishop except for the single path Z - X - Y where X is the central vertex and Y, Z are, respectively, the upper-right and lower-left corners (Fig. 3). Therefore the coloring used in the proof of Theorem 2.3 will use the last color only on X - Y. □ A version of Lemma 2.4, with proof similar to the one given, but requiring some color switching, holds for even bishops; we do not need the result so just sketch the proof. Lemma 2.5. The bishop graph B2k,2k admits a class-1 coloring where one of the colors appears on only 2 edges; and the 2 cannot be replaced by 1. 185 Ars Math. Contemp. 13 (2017) 275-291 o o o o ® o o o o o o o ® o o o o o o o © o o o o Figure 3: The edges shown form the subgraph G- of B55. This subgraph consists of many isolated edges and one 2-edge path: Z — X — Y, and so can be edge-colored so that one color occurs only once, at X — Y. Sketch of proof. The proof focuses on the white bishop and uses some color switching in the subgraphs G- and G+-1 to get the uniquely appearing color at the edge connecting the two major vertices. That 2 is best possible follows from the fact that the graph splits into two isomorphic components. □ In fact, this whole discussion can be generalized. Let M(G) be the number of major vertices of G. Then in any coloring of G using A(G) colors, each color must occur at least I" 1M] times (because all colors appear at every major vertex). Moreover, a coloring using the rarest color exactly " 1M] times cannot exist unless there is a perfect matching (or almost perfect matching if M(G) is odd) of the major subgraph, since such a matching is needed to make each account for two major vertices. Call a class-1 coloring of G extremal if the rarest color occurs exactly "2> M1 times. Then Lemma 2.4 states that Bn,n admits an extremal class-1 coloring when n is odd, and Lemma 2.5 implies that Bnn does not admit such a coloring when n is even. Computations support the following conjecture, where WB denotes the white bishop graph. Conjecture 2.6. WBm,n always admits an extremal class-1 coloring. 3 Queen graphs The graph of queen moves on an m x n chessboard is the queen graph Qm,n (Fig. 4 shows Q3j3). The vertices of Qm,n are arranged in an m x n grid and each vertex is adjacent to all vertices in the same row, in the same column, and on the same diagonal or back diagonal. We always assume m < n. Easy counting and summation leads to ( 3m + n — 5 if m = n and n is even A(Qm,n) = \ ^ . , I 3m + n — 4 otherwise ne(Qm n) = im(2 — 2m2 — 12n + 9mn + 3n2). 6 W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 Figure 4: The queen graph Q3,3 has 28 edges and maximum degree 8. It combines the bishop graph (blue) with the rook graph (red). Queen graphs have served as a challenging benchmark for vertex coloring algorithms [1]. The values of x(Qn,n) are known for n < 26. For 11 < n < 26, x(Qn,n) = n; the first open case is Q27,27. So a case involving 272 = 729 vertices is unresolved. As discussed later in this section, we developed an algorithm that succeeds in finding the edge-chromatic number for cases as large as Qh,7o7, which has 7777 vertices and requires coloring almost three million edges. But many cases are resolved by relatively straightforward arguments and Theorems 3.1 and 4.1 find the edge-chromatic number in all cases except when m, n are odd and 2(m2 - 3m + 4) < n < 3(2m3 - 11m + 12). Any queen graph is the edge-union of a bishop subgraph and a rook subgraph (Fig. 4); the maximum degrees add: A(Qm,n) = A(Bm,n) + A(Rm,n). Theorem 2.3 shows that all bishop graphs are class 1 and Theorem 2.2 shows that the rooks are class 1 except when both m and n are odd. Thus one can often get a class-1 queen coloring by forming the union of optimal colorings of the bishop and rook subgraphs. When the rook is class 1, one can simply combine class-1 colorings for the rook and bishop to get a class-1 queen coloring. This yields the class-1 part of the next theorem in all cases except one: Qn,n, n odd. Theorem 3.1 (Joseph DeVincentis, Witold Jarnicki, and Stan Wagon). The queen graph Qm,n is class 1 if at least one of m and n is even, or if m and n are equal and odd. The graph is class 2 if m and n are odd and n > 3 (2m3 — 11m + 18). Proof. The last assertion follows from the fact that Qm,n in that case is overfull and therefore is class 2. This is because the overfull condition becomes — (mn — 1)(3m + n — 4) < — m(2 — 2m2 — 12n + 9mn + 3n2) — 1, 26 which simplifies to the stated inequality n > 1 (2m3 — 11m + 18). The class-1 result is proved by combining class-1 colorings of the rook and bishop subgraphs, except in the one case that the rooks are class 2. Thus a different argument is needed for Qn,n where n is odd. Consider Qn,n with n odd. The central vertex is the only vertex of maximum degree, so the result follows from Fournier's theorem (§1). It also follows from Theorem 4.1 below, but we can give a direct construction of a class-1 coloring, using a special property of the square bishop graph. 187 Ars Math. Contemp. 13 (2017) 275-291 Start with a coloring of Bn,n as in Lemma 2.4. Then we can color the corresponding rook graph Rn?n using only new colors in such a way that a color is free to replace color 2n - 2 at its single use on the bishop edge X — Z. The result will be a class-1 coloring of Qn,n. ro in \Q f> oo ON © © © © © © © iS iS C4 iS C4 iS iS iS iS C4 iS C4 iS iS r^ r^ ra in ra r^ r^ r^ r^ ra r^ ca r^ r^ CO CO CO CO CO CO CO r^ r^ ra r^ ra r^ r^ t t t t t t t r^ r^ ra r^ ca r^ r^ in in in ^ in in in r^ r^ ra r^ ra r^ r^ Figure 5: A class-2 coloring of R7,7 with color 25 placed so it does not interfere with the bishop edge X - Z; therefore 25 can replace 12 on that bishop edge, reducing the total color count to the desired 24. We will build a class-2 coloring of Rn,n using colors 2n - 1,..., 4n - 3, which are unused in the bishop coloring (recall A(Rn,n) = 2n - 2). Color each row with 2n -1,..., 3n - 2 so that this order indicates the missing colors in each row (Fig. 5). Now color the columns by using the remaining colors together with the appropriate missing color; e.g., the first column gets colors 3n - 1,..., 4n - 3 together with 2n - 1. Arrange the column coloring so that the missing colors at the rows are in reverse numerical order (as in Fig. 5), except that, in the central column, color 4n - 3 is missing at the central vertex X. Then we can finish by replacing color 2n - 2 on X - Z in the bishop coloring by color 4n - 3 (25 in Fig. 5). So the total number of colors used is now 4n - 2, and combining the two colorings gives a class-1 coloring of Qn,n. In fact, it is a also an extremal coloring (see end of §2), as the rarest color appears only once. □ Returning to the general edge-coloring questions left open by Theorem 3.1, the most natural conjecture is that Qm,n is class 1 whenever it is not overfull. The first cases are: Q3,n, 3 < n < 11; Q5,n, 5 < n < 69; Q7,n, 7 < n < 207; Q9,n, 9 < n < 457; and Qii,n, 11 < n < 851. Conjecture 3.2. The queen graph Qm,n is class 2 iff it is overfull. We have some positive steps toward Conjecture 3.2. A first step was a generalization of the Qm,m case that combined bishop and rook colorings and worked for m < n < 2m - 1; W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 we omit the details because Theorem 4.1 in §4 uses more delicate arguments to get the much stronger result that Qm,n is class 1 when m < n < 1 (m2 - 3m + 2). For small values (e.g, m = 3,5) the quadratic result is not as good as the 2m - 1 result, but that is not a problem because various computations, which we describe in a moment, show that Conjecture 3.2 is true for m < 9. If f (m) = 1 (2m3 - 11m + 18), then Qm,f (m) is "just overfull" [20, p. 71], in that ne = A [2nv\ + 1. The Just Overfull Conjecture [20, p. 71] states that for any simple graph G such that A(G) > 2nv (G), G is just overfull iff G is "edge-critical" (meaning, x' decreases upon the deletion of any edge). Computations show that Q3,i3 is edge-critical. Since deletion of a single queen edge cannot reduce the maximum degree, this is the same as saying that the deletion of any queen edge leads to a class-1 graph. So we have the following additional conjecture about the structure of queen edge colorings. Conjecture 3.3. The queen graph Qm,n is just overfull iff it is edge critical. An algorithm based on Kempe-style color switches yielded class-1 colorings for queen graphs that verify Conjecture 3.2 for m = 3, 5, 7,9, and for m = 11 up to n = 551. A straightforward bootstrapping approach, where Qm,n was used to generate a precoloring for Qm,n+2 and random Kempe color-switches were used to resolve impasses, worked for m = 3 and 5 (and 7 up to Q7,199); an example of a class-1 coloring of Q3,7 is in Figure 6; it was found by a method similar to the general Kempe method, but with an effort to find an extremal bishop coloring, which is shown at top with white the rarest color. But a more subtle method yielded a much faster algorithm, which resolved Conjecture 3.2 for m = 7 and 9 (and 11 up to Q11,ss9, and also Qn,707). The largest case required the coloring of 2,861,496 edges! This faster algorithm uses an explicit method to get a A + 1 coloring (e.g., one can combine optimal colorings of the rook and bishop subgraphs) and then Kempe-type switches to eliminate the least popular color. This last step is based on a local search method that assigns a heuristic score to the possible switches and chooses the one with the highest score. This approach is quite general, using no information specific to the queen graph (except the speedy generation of the initial A + 1 coloring, a task that can also be done via the algorithm inherent in Vizing's proof that a coloring in A + 1 colors always exists). 4 Quadratic class 1 queen graphs In this section we show how a certain multigraph defined from the canonical bishop coloring can help prove that many queen graphs are class 1; the method can be called the ring-and-ladder method. Throughout this section m and n are odd, m < n, and k = 2(m - 1). The main result, proved in §4.2, is the following. Theorem 4.1. Qm,n is class 1 for all m < n < 1 (m2 - 3m + 2). 4.1 The derived ring of a bishop coloring We will here use only the canonical path-based class-1 coloring of the bishop graph Bm n, as described in Theorem 2.3. From such a coloring, we can define a derived multigraph; edge-coloring information about the multigraph can yield edge-coloring information about the corresponding queen graph Qm,n. The multigraph is in fact a ring, by which we mean a multigraph on vertex-set V with edges being edges of the associated simple cycle on V. 189 Ars Math. Contemp. 13 (2017) 275-291 975134 81526 6352 243 67 1 Figure 6: Top: An extremal edge coloring of B37; there are four colors and white is avoided at vertices 1, 2, 3, 4, 6, 16, 18, 19, and 20. The dashed arcs indicated how white can then be used on four rook edges. Take the four colors, starting with white, to be 9, 10, 11, 12. Bottom: A class-1 coloring using 1 through 8 of the rook graph R3,7 less the four edges from (a); only the vertical edges are shown as arcs in the edge-deleted graph. The four dashed white edges get the shared color, 9. The three sets of horizontal labels indicate edge colors on the horizontal edges, moving to the right. This rook coloring combines with the bishop coloring to yield a class-1 coloring of Q3,7 using 1 through 12. Note that a ring might be missing some edges from the underlying cycle; in that case it is called a multipath (it could have several connected components). In [20, p. 157], the term "ring" is used for a multigraph as we have defined it, but excluding multipaths; but allowing multipaths is a minor addition and causes no problems. Recall from Theorem 2.3 that the last two colors (2m - 3 and 2m - 2; in this section we use cyan for color 2m - 2) in the canonical bishop coloring are used on the subgraph G-, which consists of paths that start with edges of positive slope and length k, then negative slope edges of length k + 1, then positive slope edges of length k, and so on (Fig. 2, bottom right). We call such a path a special path. Definition 4.2. For any bishop graph Bm,n, let Bm,n, the derived ring, be the multigraph on vertices {1,2,..., m} given in the order {1 + jk : j = 0,..., m — 1} (where the numbers are reduced mod m starting from 1); the edges arise from the (2m - 2)-colored bishop edges: the bishop edge (xi, yi) - (x2, y2) induces the edge y1 - y2 in Bm,n. The case of B5j11 is shown in Figure 7. The multiplicities of the edges in Bm,n ((3, 5, 3,4,4) in Fig. 7) play a key role in W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 o»o«o»o«o»o5 • o«o*o«o*o*4 o»o»o»o»o»o3 mo*omo*omo*2 o»o«o»o«o»ol Figure 7: The last color (color 8 = 2 • 5 — 2) of the canonical coloring of B5,h (left) and the derived ring B5,n with edge-multiplicities shown. The dashed edges correspond. the proof that follows. The critical parameters of Bm,n are A and x', and the minimum multiplicity We also use the maximum multiplicity and am n, the edge-count of Bm,n (i.e., the number of cyan edges in the canonical coloring). Now here is the key result that relates the chromatic index of Bm,n to that of Qm,n. Proposition 4.3 (The Ring-and-Ladder Method). Suppose Bm,n can be edge-colored using n — 1 colors. then Qm,n is class 1. That is, x'(Bm,n) < n — 1 implies x'(Qm,n) = 3m + n — 4. Proof. We start with a special class-2 coloring (a "ladder coloring") of Rm,n using colors {1, 2,..., m—n —1}. Because the rook graph is regular, each vertex in any class-2 coloring misses exactly one color. We start by using 1 through m on the columns (and some row edges), and will then use the n —1 colors A = {m+1,..., m+n — 1} on the uncolored row edges. Each vertex in the leftmost column will use all colors in A, but the sequence of n — 1 missing colors in each row excluding its leftmost vertex is a permutation of A; moreover, the colors in A may be arranged so that, for each row, any preselected permutation is the missing-color permutation for that row. To define the ladder coloring, use colors 1 through m on each column, ensuring that color i is missing at vertices in the ith row. Now use 1 to color the horizontal edges in the bottom row that connect vertices in successive columns after the leftmost; i.e., the edges connecting the vertices in columns 2 and 3, columns 4 and 5, and so on. Do the same for row 2 but using color 2, and so on (Fig. 8). We have now used m colors to color all vertical edges and the edges of one maximum matching in each row. But each row is a Kn, and Kn minus any maximum matching can be colored with n — 1 colors (Prop. 2.1). Thus the colors in A suffice to color all uncolored horizontal edges. The vertices in the leftmost column see all the colors in A, while the remaining vertices (which already have edges colored 1 through m) each miss exactly one color in A. Thus the missing colors in each left-deleted row form a permutation of A, and it is clear from the construction that the A-colors can be arranged independently in the rows, so that any set of m permutations can be assumed to be the missing-color permutations on the rows, excluding the leftmost vertices. The proof of the theorem now proceeds as follows. We assume that the bishop graph is colored in the canonical way (Theorem 2.3) using colors from 1 to 2m — 2. Let £ be 191 Ars Math. Contemp. 13 (2017) 275-291 8 9 10 11 12 13 1415 on all rows Figure 8: A class-2 ladder coloring of R7,g using 15 colors. The column colors are listed in missing order. the hypothesized edge-coloring of Bm,n using colors {m + 1,..., m + r}, r < n - 1; this is a subset of A. If £ assigns k to edge e = y — y' of Bm,n, assign k as a missing color to the endpoints of e viewed as a bishop edge; that is, if e arises from the (2m - 2)-colored bishop edge (x, y) — (x', y'), assign k to be used as a missing rook color at both vertices (x, y) and (x', y'). Because £ is a proper multigraph coloring of Bm,„, no k will be assigned to more than one vertex in any row; and because no bishop edge incident with the leftmost column gets color 2m - 2, no missing color will be assigned to vertices in the leftmost column. We therefore get, for each row, an injection from {m + 1,..., m + r} to the vertices of that row excluding its leftmost vertex, and these maps can be extended to full permutations of A arbitrarily. Since, in the class-2 rook coloring, we can arrange the missing A-colors to match these missing-color permutations, we can now recolor each (2m - 2)-colored bishop edge with the common missing rook color at its endpoints, thus eliminating 2m - 2 as a bishop color. So now the two colorings combine to give a coloring of Qm,n with color count equal to A(Bm,n) - 1 + A(Rm,n) + 1, which is A(Qm,n). □ We will use Proposition 4.3 to obtain an infinite family of queen class-1 colorings, but first we need careful analysis of the rings Bm,n. For general rings there is a beautiful exact formula due to Rothschild and Stemple and, independently, Gallai (see [20, Thm. 6.3]). Theorem 4.4 (Ring Chromatic Index). Let G be a ring with n vertices; then x'(G) = max A(G), ne(G) Ln/2j Proof. If G is a ring, but not a multipath, this is exactly the formula of Rothschild et al. For a multipath, x'(G) = A(G) (Lemma 4.6), and it is not hard to see that A(G) > ne (G) Ln/2j □ W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 For the regular ring Cm,a of length m with a edges in each group, this reduces to 2 am m 1 ; we here present a direct proof of the regular case that is slightly different from the proof in [20] as it avoids induction. Recall also the two classic upper bounds for multi-graphs: Vizing's bound is x'(G) < A(G) + ^+(G) and Shannon's bound is x'(G) < L 3 a(g)_|. Proposition 4.5 (Regular Ring Chromatic Index). x'(Cm,a) = m— 1 Proof. View Cm,a as a collection of a simple cycles and partition them into groups of size k = (m -1)/2, or less for the last group. Each group can be edge-colored using two colors for each cycle plus one extra color that is used on all the cycles in the group, spreading the extra color around a maximum matching in the m-cycle so that the edges with this extra color are disjoint (Fig. 9). The total color count is 2a + , which equals |"arl, as in the Proposition. This upper bound is sharp because p(Cm a) = k. If the color count was less than the upper bound, the edge count would be at most k ([|] + 2a - 1); using the identity k [|] < a + k -1 simplifies this to ma -1, one less than the number of edges. □ Figure 9: The regular ring C9,9 (shown split apart into 9 cycles) can be edge-colored using 21 colors. Each cycle gets 2 colors (for 18), with three shared colors (one for each group of four or less; red, green, blue) each placed in a matching. If m is even, then x'(m, a) = 2a, but this is irrelevant to our work. More important here is the simple case of a multipath. Lemma 4.6. If G is a multipath, then x'(G) = A(G). Proof. Enumerate the edges in the order they appear in the path as {e^ and assign color i (mod A) to ei. □ 193 Ars Math. Contemp. 13 (2017) 275-291 The preceding cases lead to a simple upper bound for any ring (this also follows from Theorem 4.4 and the easily proved ["fl < A + Corollary 4.7 (Ring Chromatic Index Bound). Let G be any ring with vertex count m. Then x'(G) < x'(Cm,M-) + A(G) — 2yr. Using k for 1 (m — 1) as usual, this becomes X'(G) < + + A(G) — 2^" = A(G) + Proof. Split G into the regular "kernel" — the ring Cm,M- — and the "residual", which is a multipath (because kernel removal leaves a 0 multiplicity) and so has chromatic index A(G) — by Lemma 4.6. The kernel is colorable as in the Regular Ring Chromatic Index Theorem, and summing the two yields the claimed bound. □ Compare the preceding bound to the general Vizing bound: x' < A + For rings, x' < A + The values p±(BBm,n) do not differ by much (in general of course they can differ arbitrarily), but division by k is a big improvement. Recall the trivial lower bound "e (G) < x'(G). For our bishop rings this becomes g('Bfcm,n < x'(Bm,n. In fact, it appears that this lower bound is always equal to the chromatic index of the derived ring. We have checked this for m < 19 and n < 199. The computation is simplified by the use of Theorem 4.4 to compute x'; by that theorem, the conjecture follows from A < for the bishop rings, and this is easy to check. Conjecture 4.8. x'(Bm,n) = T^r2!. There are many many patterns in the data one can compute for the derived ring of Bm n; key parameters are the total edge count a, the minimum multiplicity and the maximum degree A. The next conjecture summarizes the results of many computations. Figure 10 presents some evidence for Conjecture 4.9, and also shows the periodicity in the edge counts of Bmj„ that appears to arise in all cases. Conjecture 4.9. For odd m, n, with m < n, 2 mn — (1 m2 — 1) < a 1). ym,n < 2 1 1 / 2 < 1 mn — 1 (m2 + k M k k k 4.2 The fine structure of the canonical bishop coloring We can use the color-sharing theorem and a detailed study of the properties of the last color in the canonical bishop coloring to prove the queen coloring result of Theorem 4.1. Proof of Theorem 4.1. Since we have already shown that Qm,n is class 1 if either m or n is even, we assume m and n are odd and write m = 2k +1. Recall (Thm. 2.3) that in Bm,n only two colors (one of them being cyan) were needed to color all special paths. As we are at liberty to start each special path with either color, we assume that no special path starts with cyan. Let C be the set of cyan edges in all special paths. Because k and m are relatively prime, the derived multigraph is a ring. The following result will yield Theorem 4.1 as a consequence of the ring-and-ladder method (Proposition 4.3) and the Ring Chromatic Index Bound (Cor. 4.7). It is not hard to see that n — 2k < A(Bmj„). Proposition 4.10, the final step in the proof, puts an upper bound on the maximum degree; so we see that, as m is fixed and n rises, the derived ring is close to being regular. W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 -(m2 + l) 4 131 151 Figure 10: Computed values of a, — 4 (m2 + 1) (upper) and 1 - 2m Also note the periodicity of this reduced data set with period m2 — 1 (dashed blue line) m,n — mr, where m =11 and with the red lines being 2 (lower). This illustrates the bounds of Conjecture 4.9. 2 Proposition 4.10. When m andn are odd, m < n, m = 2k+1, we have A(Bm,r) < n—k. We can then complete the proof of Theorem 4.1 as follows. For any ring G, (G) < 2A(G), so by Corollary 4.7 we have x'(Bm,r) < \n — k + rkr1. By assumption, n < 2(m2 — 3m + 2) = k(2k — 1), and therefore < k — 1 so that \^ 1 < k — 1 and x'(Bm,n) < n — 1. Proposition 4.3 now concludes the proof. □ We now prove Proposition 4.10, starting with some definitions: call the leftmost vertex of a special path in a bishop graph an initial vertex and let £(i,j) be the length (i.e., edge count) of the special path that starts at the initial vertex (i, j). Furthermore, call an initial vertex (i,j) for which £(i, j) is even an even vertex and one for which £(i, j) is odd an odd vertex. For bishop vertices v viewed as points in the plane, we use v < w to mean that v is first in the lexicographic ordering: vx < wx — 1, or vx = wx and v proof into a series of claims. y < wy. We break the Claim 4.11. Let I (j) be the number of initial vertices in row j, and let O(j) be the number of odd vertices in row j. Then the degree of row j in Bm 1 — j). is deg(j) = n — I (j) — O(m + Proof. Note that the degree of a vertex in Bm,r is the number of bishop vertices in the row represented by the multigraph vertex that are incident with an edge in C. Every vertex in Bmr that is not an endpoint of a special path lies on a cyan edge, so is counted toward the degree of the row in which it sits. Because we have arranged for all paths to start on the left without cyan, we eliminate all initial vertices in the row from the count; we also eliminate all vertices in the row that terminate an odd-length path, as they will not be incident with a ir - 195 Ars Math. Contemp. 13 (2017) 275-291 cyan edge. Note that n(i, j) = (n +1 - i, m +1 - j), a vertical reflection followed by a horizontal reflection, is an automorphism of Bm,n that takes special paths to special paths (and odd length special paths to odd length special paths). Therefore if v is an odd terminal point of path p, n(v) is an odd vertex beginning path n[p]. Thus the number of vertices in row j that terminate an odd-length path is the same as the number of odd (initial) vertices in row m + 1 — j, and the claim follows. □ Claim 4.12. I(j) = k + 1 for j < k; I(j) = k for j > k. Proof. This follows from the fact that the set of initial points of all special paths is {(i, j) : (i,j) < (k + 1, k)}; see Figure 11. □ Figure 11: The values of I(j) for B7}15 are 4,4,4,3, 3, 3 (Claim 4.12); these are all the vertices lexicographically below or equal to (4,3). The yellow vertices are even, the blue ones odd. Claim 4.13. There is at least one even vertex and at least one odd vertex. Proof. Because C is a matching, e = v/2 where e = |C| and v is the number of vertices in Bm,n that are included in a C edge. But the vertices included in such an edge are those that don't begin a special path or terminate an odd-length special path. There are k(m + 1) vertices that begin a special path, so letting p be the number of odd vertices, we have e = 1 (nm — k(m +1) — p). Because nm is odd and k(m + 1) is even, this implies that p must be odd, and thus there are an odd number of odd vertices, and hence also an odd number of even vertices. □ Claim 4.14. ^(i, j) is the largest integer q such that qk + i + |_ qk+mj-1 J < n. Proof. A special path moves k units to the right (i.e., from i to i + k) when it moves upwards and k +1 units to the right when it moves downwards, and only moves downwards if ck + j < bm < (c + 1)k + j, where c is the number of edges the path has moved along thus far, and bm is any multiple of m. Thus a path that starts at (i, j) and moves to the right q edges ends at (i', j'), where i' = qk + i + |(qk + j — 1)/mJ, and the claim follows. □ W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 Claim 4.15. There is an initial vertex (i*,j*) < (k +1, k) such that £(i,j) = £(1,1) for all (i,j) < (i*,j*), and £(i,j) = £(1,1) — 1 for all initial vertices (i,j) > (i*,j*). Proof. See Figure 11 for an example where (i*,j*) = (2, 2). Let L = £(k + 1, k). It follows easily from Claim 4.14 that £(i,j) is decreasing with respect to lexicographic order; that is, (i,j) < (i',j') implies £(i,j) > £(i', j'). Thus L < £(1,1), and the inequality must be strict by Claim 4.13. Also, by Claim 4.14, we have that £(1,1) is the largest integer q such that qk + |qk J < n — 1, while L is the largest integer q such that qk + k + | qk+Jk-1 J = (q+1)k+L (q+mk-1 J < n—1. This implies that £(1,1) < L+1. Thus L < £(1,1) < L+1, and the claim follows. More precisely, (i* ,j*) is the smaller of the largest even initial point and largest odd initial point, where comparisons are lexicographic. □ Claim 4.16. If £(1,1) is odd, A(Bmn) < n — k. Proof. If £(1,1) is odd, Claim 4.15 implies that the odd vertices are all (i,j) < (i*,j*). Thus Then O(j) = O(m + 1 - j) i* if j < j * i* - 1 if j>j * i* - 1 if j < m + 1 - j* i* if j > m + 1 - j* By Claim 4.12, we therefore have I (j ) + O(m +1 - j ) ' i* + k if j < min(k + 1, m +1 - j*) i* + k - 1 if k + 1 < j max(k + 1, m + 1 - j*) Thus A(Bm,„) < n - k - i* + 1 by Claim 4.11, and because i* > 1, n - k - i* + 1 < n - k. □ We complete the proof of Proposition 4.10, and thus Theorem 4.1, with: Claim 4.17. If ¿(1,1) is even, A(Bm,„) < n - k. Proof. If 1(1,1) is even, Claim 4.15 implies that the odd vertices are all (i,j) such that (i*,j*) < (i,j) < (k + 1,k). Thus ' k + 1 - i* if j < min ( j*, k) O(j) k - i* k + 2 - i* k + 1 - i* if k < j < j* if j* < j < k if j > max(j*, k) Then O(m + 1 - j) 'k + 1 - i* k + 2 - i* k i* if j < m +1 - max( j*, k) if m +1 - k = k + 2 < j < m + 1 - j* if m + 1 - j * < j < k + 2 ^k + 1 - i* if j > m +1 - min(j*,k) 197 Ars Math. Contemp. 13 (2017) 275-291 By Claim 4.12, we therefore have I(j) + O(m +1 - j) = < m — i* + 1 m — i* m — i* + 1 m i* 1 if j < m + 1 — max(j*, k) and j < k if j < m + 1 — max(j*, k) and j > k if k + 2 < j < m + 1 — j* if m + 1 — j * < j < k if m + 1 — j* < j = k + 1 if j > m + 1 — min(j*, k) Note that if i* = k + 1, j* must be less than k (by Claim 4.13), and thus the fifth of these cases (m +1 - j * < k +1) cannot occur. In that case, A(Bm,n) < n - m + i* = n — m + k + 1 = n — k by Claim 4.11. If i* < k + 1, we similarly have A(Bm,n) < n — m + i* + 1 < n — k, and the claim follows. □ * mi mi 4.3 Limits to the ring-and-ladder method The quadratic lower bound, n > 1 (m2 — 3m + 4), for class-2 queen graphs of Theorem 4.1 provides substantial support for the queen chromatic index conjecture (Conjecture 3.2). Assuming the truth of Conjecture 4.8, we can improve the bound slightly, likely up to 2 (m2 + 2m — 3), but the ring-and-ladder method will not reach beyond a quadratic bound and thus will not settle the full Conjecture 3.2. For suppose that 2m — 1 < n; then the number of major vertices in Bm,n is mn — 2m(m — 1) + 2k+4 E¿=1 i = mn — (3m +1)k; therefore, for such n, any bishop color class from a class-1 coloring must have size at least a = 1 (mn — (3m + 1)k — 1) + 1. Now suppose that x'(Bm,n) < n — 1; then Bm,n is covered by at most n — 1 matchings, each of size at most k, and thus Bm,n can have at most b = k(n — 1) edges. But this is the same as the size of the (2m — 2)-color class, so we must have a < b, which simplifies to n < | m2 — 2m — 1 .In fact, assuming the truth of Conjecture 4.9, the ring-and-ladder method can only work up to about m2. For then om,n > 2mn +1 — 2m2. Therefore x'(Bm,n) > (2mn + 1 — 2m2)/k. Now for this to be at most n — 1 means n < m2 — m — 1, so this is a likely bound for the ring-and-ladder method. Thus a quadratic bound is the best we can achieve with our methods, and a proof of Conjecture 3.2 would seem to require an altogether different approach of even greater intricacy. This highlights the surprising difficulty of the Vizing classification problem for queen graphs. It is well known that the general classification problem is NP — complete ([20, p. 18]), but one would expect that queen graphs — being a union of rook and bishop graphs whose classifications are relatively straightforward — would be amenable to a complete classification. So as we leave behind the quadratic bound obtained here, it is hard to resist the thought that we may be entering terrain of intractable complexity. If so, the computational evidence supporting Conjecture 3.2 seems all the more remarkable and may be the best we can hope for. 5 Mycielski graphs The Mycielskian ^(G) of a graph G with vertex set X is an extension of G to the vertex set X U Y U {z}, where |Y| = |X| and with new edges z — for all i and x — y- for each edge Xj — xj in G (see Fig. 12). The Mycielski graphs Mn are formed by iterating W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 p on the singleton graph M1, but ignoring the isolated vertex that arises in p(M^. Thus Mi = Ki, M2 = K2, M3 = C5, and M4 is the Grotzsch graph (Fig. 13). They are of interest because Mn is a triangle-free graph of chromatic number n having the smallest possible vertex count. Fisher et al. [8] proved that if G is Hamiltonian, then so is p(G). We extend that to a Hamilton-connected (HC) result, provided nv (G) is odd. This is sufficient to show that all Mycielski graphs Mn, except M3 = C5, are HC. Figure 12: The Mycielskian of the 6-path formed by the lowest six vertices. Figure 13: A Hamiltonian cycle in the Mycielski graph M4, which is the Grotzsch graph. The key result is the following. Theorem 5.1. If G is an odd cycle, then p(G) is Hamilton-connected. We will prove this shortly; note that it yields the fact that p preserves HC for graphs with an odd number of vertices. Corollary 5.2. If G is Hamilton-connected and nv (G) is odd, then p(G) is Hamilton-connected. Proof. We may skip the trivial case that G has one vertex. Therefore G is Hamiltonian, with Hamiltonian cycle C. Since p(G) contains p(C) as an edge subgraph, and since p(G) is HC by Theorem 5.1, so is p(G). □ Theorem 5.1 does not extend to the even case. Proposition 5.3. If G is an even cycle, then p(G) is not HC. Proof. It is easy to use parity to show that there is no Hamiltonian path from any vertex in X to z. This is because such a path can get to z only from Y, and hence must alternate from X to Y; but then if the path starts at x1 it can never visit Xj, where i is even. □ 199 Ars Math. Contemp. 13 (2017) 275-291 Even cycles are not HC, so the negative result for even cycles does not mean that HC-preservation fails in general for even graphs (an exception being K2: ^(K2) is a 5-cycle, which is not HC, even though K2 is HC). Computations support the following strengthening of Corollary 5.2, but some new ideas are needed. Conjecture 5.4. If G is Hamilton-connected and not K2, then ^(G) is Hamilton-connected. Easy computation shows that M4, the 11-vertex Grotzsch graph, is HC and so Corollary 5.2 means that all Mycielski graphs are HC, except the 5-cycle M3. Corollary 5.5. The Mycielski graph Mn is Hamilton-connected iff n = 3. The stronger assertion that ^(G) is HC whenever G is Hamiltonian is false. Counterexamples include C4, K3,3, K112, Grid2,3. Indeed, the first two here are Hamilton-laceable, but their Mycielskians are not HC. Proof of Theorem 5.1. Assume that the cycle G has n vertices, given in cyclic order as X = [xi}, where n is odd. Then ^(G) has as vertices X, and also Y = {yi} and a single vertex z. The subgraph corresponding to Y U {z} forms a K1jn. Then, as in [8], we have the following Hamiltonian cycle in ^(G) (see Fig. 14): C = yi — x2 — y3 — X4 — • • • • • • — Xn-1 — yn — Xi — Xn — yn-1 — • • • — y4 — X3 — y2 — z — yi Figure 14: A Hamiltonian cycle in the Mycielskian of an odd cycle {Xi}. Now consider any two distinct vertices A, B of ^(G). Case 1. A — B is an edge in ^(G). It suffices to show that there is a Hamiltonian cycle containing A — B. By symmetry, we may assume A — B is one of x1 — Xn, x1 — yn, or y1 — z. In all cases cycle C above contains the edge. Case 2. A — B is not an edge of ^(G). Case 2.1. [A, B} c X; say xi, Xj. Without loss of generality, assume i = 1. The same proof works for both even and odd j. Zigzag up from x1 until yj-1 is reached (when reaching the end, carry on at the W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 beginning in the obvious way). Then jump via z to yn and zigzag left (past yi if necessary) until xj is reached. Formally: xi - y2 - X3 - • • • - yj-i - z - yn - Xn-i - yn-2 - • • • - Xj. Figure 15 shows how this works when j is even, followed by the odd j case. xl to xeven Figure 15: Typical Hamiltonian paths from X to X. Case 2.2. A e X and B e Y. Assume A = xi and B = yj. Then xi - Xj is a nonedge in G. If j is even: Zigzag up to xj-i - xj then zigzag to yn - z - yj-i and zigzag left and through yi to the target xj, as in Figure 16. Xi to ^even Figure 16: A typical Hamiltonian path from X to an even vertex in Y. If j is odd, zigzag up to xj then left to xj -i and down through yi to yj+i, then up to z and yn and zigzag down to the finish at yj, as in Figure 17. This works fine even if j = n. Case 2.3. A e X and B = z. Assume A = xi . Zigzag through to yn and then finish up at z: xi - y2 - x3 - y4 - x5 - y6 - • • • • • • - xn - yi - x2 - y3 - x4 - y5 - • • • - yn - z; 201 Ars Math. Contemp. 13 (2017) 275-291 Xi to jodd Figure 17: A typical Hamiltonian path from X to an odd vertex in Y. Figure 18: A typical Hamiltonian path from X to z. see Figure 18. Case 2.4. {A, B} c Y. Assume first that A = y1 and B = y, with j even. Jl to Jeven Figure 19: A typical Hamiltonian path from a vertex in Y to a vertex of different parity in Y. Zigzag up from y1 to yj-1, then up to z and down to yn, then back to x1 and zigzag up to xj_1, then to Xj and zigzag up to xn-1, then xn and zigzag down to y. See Figure 19. Formally: y 1 - X2 - y3 - • • • - yj-1 - z - yn - X1 - y2 - X3 - • • • • • • - Xj_1 - Xj - yj+1 - Xj+2 - • • • - Xn_1 - Xn - yn_1 - Xn_2 • • • - yj Finally assume j is odd. Zigzag from y1 to Xj_1, then back to Xj_2 and zigzag down to x1 and up to yn, then up to z, down to yj_1, and zigzag up to Xn, then back to Xn_1 and zigzag to yj; see Figure 20. This completes the proof. □ W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 Ji to jodd Figure 20: A typical Hamiltonian path from a vertex in Y to a vertex of the same parity in Y. The proof technique does not work directly to settle the even case. But we have barely used the edges in G; because G is assumed HC, there might be a way to use more of those edges to extend Corollary 5.2 to all graphs, proving Conjecture 5.4. Computation also leads to a conjecture about edge coloring. All the Mycielski graphs (except M3) are class 1 because of Fournier's theorem (§ 1); for M4 and beyond, z is the unique vertex of maximum degree. But perhaps much more is true: computation supports the following conjecture. Conjecture 5.6. For any graph G other than K2, m(G) is class 1. 6 Keller graphs The Keller graph Gd of dimension d is defined as follows [6, 21]: the 4d vertices are all d-tuples from {0,1,2, 3}. Two tuples form an edge if they differ in at least two coordinates and if in at least one coordinate the difference of the entries is 2 (mod 4). We ignore Gi, which simply consists of four isolated points. These graphs are vertex transitive and therefore regular; it is easy to work out the degree of Gd, which is 4d - 3d - d. The graph G2 is also known as the Clebsch graph. The Keller graphs play a critical role in the Keller conjecture [6], which, in its unrestricted form, states that any tiling of Rd by unit cubes contains two cubes that meet face-to-face. This conjecture is closely related to w(Gd). The value of w(Gd) is known for all d: when d > 8, w(Gd) = 2d, while w(Gd) < 2d for d < 7 (Table 2; see [6]). These w values imply that the Keller conjecture with the restriction that all cube centers involve only integers or half-integers is true for d < 7 and false for d > 8. The unrestricted Keller conjecture is known to be true for d < 6 and false for d > 8, but is unresolved in R7. Note that Gd always admits a 2d-vertex coloring, defined this way: There are 2d vertices using only 0s and 2s; they each receive a distinct color. Give any other vertex (vj) the same color as (2 [V^J); the "differ by 2" condition is never satisfied by both vertices (vj) and (2 LfJ). Therefore x(Gd) < 2d (proved independently by Fung [11] and Debroni et al. [6]). This coloring is also implicit in the proof of Theorem 6.4 below: the 0-and-2 set is the diagonal of the array shown. We will show in Corollary 6.5 that this coloring is optimal for all d. A classic theorem of Dirac [2, Thm. 4.3] states that a graph with minimum degree greater or equal to nv/2 is Hamiltonian; this applies to Gd when d > 3. We can give an explicit Hamiltonian cycle for all Keller graphs. 203 Ars Math. Contemp. 13 (2017) 275-291 Theorem 6.1. All Keller graphs are Hamiltonian. Proof. For G2, a Hamiltonian cycle is (00, 23, 01, 20, 02, 21, 03, 22,10, 33,11, 30,12, 31,13, 32). This ordering alternates 0 and 2 in the first coordinate for the first half, and then 1 and 3. And in the second coordinate, the leading 0s and 1s are matched, in order, with 0, 1, 2, 3, and the 2s and 3s with 3, 0, 1, 2. For larger d, just append vectors to the scheme for G2, thus: (00X, 23X, 01X,..., 13X, 32X, 00 Y, 23Y,...), where X, Y,... exhaust all tuples in Z^-2. This repetition still yields a cycle and because all vertices are included, it is Hamiltonian. □ Another classic result [15] states that if the minimum degree of G is greater than or equal to 2 (nv + 1), then G is Hamilton-connected. The condition holds for Gd when d > 3 and a simple computation using an algorithm described in [7] verifies that G2 is Hamilton-connected, so all Keller graphs are HC. The Keller graphs are vertex-transitive and so provide an infinite family of examples for the conjecture in [7] that vertex-transitive, Hamiltonian graphs — except cycles and the dodecahedral graph — are HC. Computations also support the conjecture that Keller graphs have Hamiltonian decompositions (meaning that the edges can be partitioned into disjoint Hamiltonian cycles, plus a perfect matching if the degree is odd; see Fig. 21 for such a decomposition of G2). We found Hamiltonian decompositions up through G6 and conjecture that they exist for all Keller graphs. Table 1 shows such a decomposition for G3: 17 Hamiltonian cycles. Figure 21: A Hamiltonian decomposition of G2, also known as the Clebsch graph: two Hamiltonian cycles (red, blue) and one perfect matching (black). The gray vertices are a maximum independent set. Conjecture 6.2. All Keller graphs have a Hamiltonian decomposition. Conjecture 6.2 is related to deep work of Kiihn et al. [12, 5]. Theorem 1.7 of [12] implies that for sufficiently large odd d, there is a Hamilton decomposition of Gd, while W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 41 27 54 26 46 30 45 9 22 58 43 25 24 44 59 37 62 2 9 32 62 60 36 19 31 31 19 53 49 19 1 50 35 22 45 50 27 55 38 54 8 17 52 48 44 58 33 11 25 1 61 21 42 60 20 20 8 49 62 46 59 52 12 23 16 63 51 7 46 48 14 49 53 2 30 29 15 32 62 18 28 40 16 43 21 16 17 56 15 14 32 21 50 41 11 6 44 51 19 41 50 55 53 41 42 52 16 56 15 56 5 29 12 14 21 26 3 24 16 7 34 1 19 51 22 39 27 3 22 40 39 57 63 17 46 58 28 59 40 25 29 44 33 49 34 40 17 46 43 49 15 32 27 62 49 33 51 39 9 12 7 40 30 56 22 9 21 45 10 17 8 23 26 9 12 7 7 38 49 24 29 51 2 52 31 12 35 39 25 57 39 2 42 40 32 56 2 36 31 59 27 36 21 59 17 16 20 13 33 3 50 8 30 26 5 21 22 5 9 3 41 47 62 29 42 25 58 22 18 4 54 42 59 16 39 46 8 19 1 7 52 33 52 23 4 52 18 27 51 61 6 60 55 47 54 27 43 12 47 58 29 43 45 42 3 18 35 56 31 28 2 18 48 13 34 3 17 5 61 54 19 13 24 4 34 4 18 16 53 25 46 10 61 42 46 52 47 57 51 35 42 13 46 60 59 12 32 37 45 16 35 6 34 22 16 61 9 16 54 7 22 45 50 42 14 22 43 41 52 14 13 26 31 38 56 46 57 53 5 28 24 4 58 45 18 63 42 63 28 53 61 1 3 29 47 34 49 10 63 18 14 9 17 9 5 61 46 25 10 53 58 6 9 43 51 53 48 41 59 60 17 35 27 10 3 43 17 32 30 19 37 40 26 24 31 26 21 54 15 29 4 57 17 10 22 39 56 31 13 36 63 7 56 39 25 1 59 38 15 24 37 55 11 23 48 37 18 36 37 28 28 58 25 33 28 20 34 4 61 42 30 26 19 32 50 59 6 59 36 11 58 34 54 15 60 17 2 58 60 29 15 16 23 13 20 3 53 2 1 16 33 25 51 40 48 42 43 5 9 63 31 50 26 59 60 43 30 6 7 33 58 22 6 3 40 47 6 50 57 44 19 23 18 48 48 32 43 8 52 20 33 3 5 36 21 24 2 60 13 57 46 57 12 48 44 42 63 4 29 30 10 27 61 35 20 32 35 23 63 38 8 62 49 33 34 6 55 60 63 15 56 61 50 49 37 37 5 38 56 26 9 26 8 19 58 54 25 51 23 11 41 28 47 31 3 20 17 32 50 22 49 34 15 34 53 57 47 12 4 52 39 59 51 11 5 52 28 3 27 22 43 27 55 38 62 58 28 49 25 27 38 51 23 57 44 50 36 12 57 33 24 21 31 36 47 18 35 15 23 9 51 7 4 11 26 1 24 51 56 59 8 55 62 7 53 45 49 58 41 32 49 51 23 3 37 25 1 41 18 53 29 25 1 31 24 23 30 55 45 47 37 8 39 8 27 27 24 49 55 36 56 60 17 53 45 4 20 44 45 63 26 45 62 6 24 27 2 18 54 59 29 3 41 46 42 53 7 55 7 40 15 32 13 25 59 61 13 38 10 55 28 28 39 14 13 13 48 9 43 36 47 30 47 21 1 48 37 63 58 6 5 19 20 41 37 19 7 29 54 12 28 46 23 27 18 21 44 33 63 26 1 2 5 60 4 14 55 53 56 44 16 10 43 10 8 21 32 58 28 23 29 15 38 1 35 2 5 49 41 2 20 16 47 3 44 10 12 63 40 63 39 25 57 43 18 13 48 48 52 7 9 50 56 37 41 46 22 10 31 17 8 11 11 14 9 17 33 40 8 54 1 39 11 57 19 38 8 34 33 48 36 63 50 27 54 42 23 26 44 34 11 21 62 35 7 13 29 46 1 23 2 29 36 14 61 4 44 44 11 39 12 30 53 37 12 7 15 39 55 15 35 21 62 13 15 35 61 22 37 19 62 30 17 42 45 5 29 13 14 20 52 55 45 4 24 61 1 32 51 55 20 11 62 35 47 33 18 24 60 38 2 54 19 31 6 41 14 44 41 23 26 41 10 61 14 6 44 46 44 62 62 31 6 43 55 32 53 52 50 52 6 8 35 30 8 21 24 48 55 34 25 9 14 60 14 30 38 40 30 58 52 51 48 1 38 24 16 62 45 22 30 20 20 13 14 57 20 2 11 28 32 40 59 10 36 6 49 38 45 34 4 28 39 12 20 37 5 57 35 5 40 12 37 10 2 63 36 54 54 3 5 31 15 11 47 10 60 26 54 60 50 11 30 45 48 31 56 61 33 43 40 4 47 16 4 21 36 60 19 61 12 34 57 38 36 56 6 18 40 14 38 39 35 47 34 50 11 42 57 33 10 Table 1: A decomposition of G3 into 17 Hamiltonian cycles. The vertices are encoded, using base 4, by integers from 0 to 63. Because A = 34, there are 17 Hamiltonian cycles. 205 Ars Math. Contemp. 13 (2017) 275-291 the improvement in [5, Thm. 1.1.3] handles the even case too. So for sufficiently large d, Gd is known to have a Hamiltonian decomposition. Our algorithm for finding these decompositions starts with the simple idea of trying random class-1 colorings (obtained by using the methods of Vizing andKempeonarandom permutation of the graph) and checking to see if the color-sets, which are matchings, can be paired up to form the desired cycles; the pairing is generally done using the classic blossom algorithm of Edmonds. A more sophisticated approach is needed for large cases such as G5 and G6. We again start with a class-1 coloring, but then apply Kempe switches in the hope of obtaining pairs of matchings that link to form cycles. The heuristic used to decide which Kempe switches to make is a scoring function that compares the number of Hamiltonian cycles obtainable by pairing up matchings (primary key), the minimum number of cycles a pair of remaining matchings produces (secondary key), and the total number of cycles that all pairs of remaining matchings produce (tertiary key). Additionally, a Hamiltonian decomposition of a significant part of the edges of G6 can be effectively constructed from a decomposition of G5. Therefore, to find a decomposition of G6, we first find one for G5. We then apply the local search method using the heuristic function described above, but only to the subgraph of G6 consisting of the uncovered edges. Although it seemed plausible that connected, vertex-transitive graphs always have Hamiltonian decompositions (excluding a few small examples), that was recently shown by Bryant and Dean [3] to be false. An even stronger property is that of having a perfect 1-factorization: a collection of matchings such that any two form a Hamiltonian cycle. That is a much more difficult subject — it is unresolved even for complete graphs — and all we can say is that an exhaustive search established that G2 does not have a perfect 1-factorization. In the other direction, a weaker conjecture than the false one just mentioned is that all vertex-transitive graphs with even order are class 1 except the Petersen graph and the triangle-replaced Petersen graph; no counterexample is known. Note that an even-order graph with a Hamiltonian decomposition is necessarily class 1. One can show that all Keller graphs are class 1 by explicit computation up to G6 and then calling on a famous theorem of Chetwynd and Hilton for the rest ([4]; see also [20, Thm. 4.17]); their theorem applies to graphs for which A > 2 (V7 - 1)nv, which holds for G7 and beyond. But in fact there is a uniform and constructive way to present class-1 colorings of all Gd, which we now describe. Note that this result also follows from the class-1 conjecture of the preceding paragraph. Theorem 6.3. All Keller graphs are class 1. Proof. All arithmetic here is mod 4. Call a vertex — a d-tuple — even if all entries are even; otherwise odd. The class-1 coloring can be constructed explicitly as follows. Define the color set S to consist of all vertices whose coordinates have at least one 2, but excluding the d vectors consisting of just d - 1 0s and one 2. This set is a type of kernel: the set of all differences u — v for edges v — u. This set satisfies (1) |S| = A, and (2) for each vertex v, its neighbors are v + S. Partition S into its even vectors, S0, and its odd ones, S1. For each s G S1, define an equivalence relation on the vertices: u v iff u — v is a multiple of s. Each equivalence class has the form {v, v + s, v + 2s, v + 3s}; because s is odd, each such class has four distinct elements. Note that the collection of classes for s is identical to the collection of classes for —s. For each s g S1, define a choice set Cs for the equivalence classes; use the lexicographically first vector in each class. Then Cs = C-s. Define the edge coloring as follows (see Fig. 22). For each even color s g S0, use it W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 for all edges v — v + s. Each s colors 1 nv edges because v — v ± s both get color s, but are the same edge (because s = — s). So in all, this colors 2nv |S0| edges. For each odd color s € Si, use it for the edges v — v + s and v + 2s — v + 3s, but, in both cases, only for vertices v € Cs. Because |Cs | = 4 nv, each color applies to 2nv edges, and so the odd colors taken together color 1 nv |Si| edges. Thus the number of edges that are colored is 2 nv (|S0| + |S1|) = 1 nv |S| = 1 nv A = ne, the total number of edges. Claim. Every edge receives only one color. Proof. Given edge u — w, let s = w — u. If s is even, then s = — s and this easily yields the claim. The odd case is more delicate. Suppose u — w is assigned color s; then s = ±(w — u). We may assume s = w — u. If the edge is assigned another color distinct from s, that color must therefore be — s. Now u and w are equivalent under both relations and ~_s. And the class representatives from Cs and C_s agree. This means that u — w must be one of the edges {v — v + s, v + 2s — v + 3s} and also one of the edges {v — v — s,v — 2s — v — 3s}. But the latter set equals {v + 3s — v, v + s — v + 2s}, which is disjoint from the first pair. □ The claim and the fact that ne edges are colored means that every edge receives a color. So it remains only to show that the coloring is proper. Suppose not. Then we have edges u — w and u — y receiving the same color s. If s is even, this is not possible because the edges would have to be of the form v — v + s and v — v — s, which are equal because s = —s. Suppose s is odd and color s is assigned to edge u — w. If u € Cs, then w = u + s;if u = v + s where v € Cs, then w = v; if u = v + 2s where v € Cs, then w = v + 3s, and if u = v + 3s where v € Cs, then w = v + 2s. In all cases there is only one choice for w. □ colors S size- 4 equivalence classes of vertices with edges colored by the odd element of S 23 00- - 23 02 - 21 01 - 20 03 - 22 10 - 33 12 - 31 11 - 30 13 - 32 21 00- - 21 02 - 23 01 - 22 03 - 20 10 - 31 12 - 33 11 - 32 13 - 30 32 00- - 32 20 - 12 01 - 33 21 - 13 02 - 30 22 - 10 03 - 31 23 - 11 Oi Id 12 00- - 12 20 - 32 01 - 13 21 - 33 02 - 10 22 - 30 03 - 11 23 - 31 even { 22 00- - 22 01 - 23 02 - 20 03 - 21 10 - 32 11 - 33 12 - 30 13 - 31 Figure 22: The class-1 Keller coloring for the edges of G2, using five colors. The even case has only one entry; S0 = {22}. The odd case has four colors and the four equivalence classes of the full vertex set are shown, with the matchings within each class. Note that the classes for ±s are the same sets (e.g., s = 12 and 32). We can also investigate some familiar parameters for Keller graphs. The standard parameters a, 0, x, and Xfrac are defined in §1. Let 0frac be the fractional clique covering number (same as xfrac of the complementary graph). Table 2 shows the known results, including results proved here. It is clear that a(Gd) > 2d since the tuples using only 0s 207 Ars Math. Contemp. 13 (2017) 275-291 d all d 2 3 4 5 6 7 d > 8 independence number, a 5 8 16 32 64 128 2d chromatic number, x 2d 4 8 16 32 64 128 2d fractional chromatic number, Xfrac 16 5 8 16 32 64 128 2d class 1 for edge coloring; — À Yes maximum clique size, ü 2 5 12 28 60 124 2d clique covering number, 0 8 13 22 37<0<40 69 <0< 80 133 <0< 160 2d fractional clique covering number, 0frac 8 64 5 64 3 256 7 1024 15 4096 31 2d Hamiltonian, Hamilton- connected Yes Hamiltonian decomposition Conjectured yes Yes Yes Yes Yes Yes perfect 1-factorization No degree, À ¥-y'-d 5 34 171 776 3361 14190 Table 2: Properties of the Keller graphs Gd. The number of vertices of Gd is 4d and the edge count is 14d(4d - 3d - d). and 1s are independent. A larger independent set can exist, but only in G2, as Theorem 6.4 shows. Theorem 6.4. The independence number of Gd is 2d, except that a (G2) = 5. Proof. for d < 5, this was known; direct computational methods work. The anomalous case has maximum independent set {(0, 3), (1,0), (1,2), (1, 3), (2, 3)}; see Figure 21. For d = 6 or 7, one can again use computation, but some efficiencies are needed since the graphs are large. The graphs are vertex-transitive, so we may assume the first vertex is in the largest independent set. Thus, if A consists of the first vertex together with its neighbors, we can look at Hd, the subgraph of Gd generated by the vertices not in A. This is substantially smaller, and we need only show that a(Hd) = 2d - 1. That can be done by standard algorithms for finding independent sets; in Mathematica it takes a fraction of a second to show that this is the case for H6 and only a few seconds to do the same for H7. Now suppose d > 8. Recall that it is known that w(Gd) = 2d in this case (Mackey [14] for d = 8; see [6, Thm. 4.2] for larger d). As in [6], place the vertex labels in a 2d x 2d grid, called the independence square. The row position of a tuple is computed by converting 0 or 1 to 0 and also converting 2 or 3 to 1 and then treating the result as a binary number. The column position of a tuple is computed by converting 0 or 3 to 0 and also converting 1 or 2 to 1 and then interpreting this in binary. The array for G4 is shown in Table 3. The tuples in the same row of the square form an independent set because, in each digit, the value is always either 0 or 1, or it is 2 or 3. Therefore there is no position where the difference is 2 (mod 4). Similarly, the tuples in a column form an independent set. The independence square also proves that x(Gd) < 2d for any d. W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0003 0002 0013 0012 0103 0102 0113 0112 1003 1002 1013 1012 1103 1102 1113 1112 0030 0031 0020 0021 0130 0131 0120 0121 1030 1031 1020 1021 1130 1131 1120 1121 0033 0032 0023 0022 0133 0132 0123 0122 1033 1032 1023 1022 1133 1132 1123 1122 0300 0301 0310 0311 0200 0201 0210 0211 1300 1301 1310 1311 1200 1201 1210 1211 0303 0302 0313 0312 0203 0202 0213 0212 1303 1302 1313 1312 1203 1202 1213 1212 0330 0331 0320 0321 0230 0231 0220 0221 1330 1331 1320 1321 1230 1231 1220 1221 0333 0332 0323 0322 0233 0232 0223 0222 1333 1332 1323 1322 1233 1232 1223 1222 3000 3001 3010 3011 3100 3101 3110 3111 2000 2001 2010 2011 2100 2101 2110 2111 3003 3002 3013 3012 3103 3102 3113 3112 2003 2002 2013 2012 2103 2102 2113 2112 3030 3031 3020 3021 3130 3131 3120 3121 2030 2031 2020 2021 2130 2131 2120 2121 3033 3032 3023 3022 3133 3132 3123 3122 2033 2032 2023 2022 2133 2132 2123 2122 3300 3301 3310 3311 3200 3201 3210 3211 2300 2301 2310 2311 2200 2201 2210 2211 3303 3302 3313 3312 3203 3202 3213 3212 2303 2302 2313 2312 2203 2202 2213 2212 3330 3331 3320 3321 3230 3231 3220 3221 2330 2331 2320 2321 2230 2231 2220 2221 3333 3332 3323 3322 3233 3232 3223 3222 2333 2332 2323 2322 2233 2232 2223 2222 Table 3: The independence square for G4: each row and each column is an independent set. 000 001 010 011 100 101 110 111 001 000 011 010 101 100 111 110 003 002 013 012 103 102 113 112 002 003 012 013 102 103 112 113 030 031 020 021 130 131 120 121 031 030 021 020 131 130 121 120 033 032 023 022 133 132 123 122 032 033 022 023 132 133 122 123 300 301 310 311 200 201 210 211 301 300 311 310 201 200 211 210 303 302 313 312 203 202 213 212 302 303 312 313 202 203 212 213 330 331 320 321 230 231 220 221 331 330 321 320 231 230 221 220 333 332 323 322 233 232 223 222 332 333 322 323 232 233 222 223 (a) (b) Table 4: (a) The independence square for G3. (b) After application of the automorphism defined by 001. Let X be a clique of order 2d in Gd. It has exactly one entry per row in the independence square. Given a d-digit bit-string b, use it to define an associated automorphism of the graph. In the positions where b has 0, leave the corresponding position of all the vertex entries alone. In the places where b has 1, do the following in those positions: switch 1 and 0, and switch 2 and 3. This preserves adjacency because positions that are different in value are still different and positions that differed by 2 (mod 4) still differ by 2 (mod 4). If the bit string is 0011, then the first two columns stay the same and the last two columns have the swaps: for example, 0213 becomes 0202. The complete action of the automorphism on G3 using the bit-string 001 is shown in Table 4. Note that this automorphism maps each row of the square to itself. The collection of automorphisms that correspond to all 0-1 bit strings will map a 2d-clique of the Keller graph to a partitioning of the vertices of the Keller graph into 2d disjoint cliques each of size 2d. So 0(Gd) = 2d for such graphs. Since any coloring of the graph can have at most one vertex per clique, for Keller graphs that have a 2d clique (i.e., for d > 8, which we have assumed), it is not possible to find an independent set of size bigger than 2d. □ Corollary 6.5. For all Keller graphs, x(Gd) = 2d. 209 Ars Math. Contemp. 13 (2017) 275-291 1 113 130 232 300 312 2 110 131 212 320 332 3 100 121 202 310 322 4 021 033 203 220 301 5 031 112 133 303 311 6 012 020 132 213 230 7 013 032 111 223 231 8 011 030 201 233 313 9 010 022 200 221 302 10 003 101 122 323 331 11 001 103 120 321 333 12 000 023 102 210 222 13 002 123 211 330 Table 5: A covering of the 64 vertices of G3 by 13 disjoint complete subgraphs. Proof. The constructive coloring at the beginning of the section gives 2d as an upper bound. Theorem 6.4 gives 2d as a lower bound, because 4d/a(Gd) = 2d. □ Fung [11, Cor. 6.7] observed that x(Gd) = 2d for d > 4, x(G3) > 7, and x(G2) > 3. Corollary 6.5 establishes the validity of x = 2d for all Keller graphs. The graph G2 is an anomaly, with independence number 5. Because xfrac(G) = for vertex-transitive graphs (see [19]), we get the following result. Corollary 6.6. If d > 3, then Xfrac(Gd) = 2d; Xfrac(G2) = 16/5. So for d > 8, we have that each parameter a, x, xfrac and w equals 2d. Computing 0(Gd) when d < 7 is difficult. A general lower bound is "J^ < 0(H), which yields 8,13, 22,37,69,133, the lower bounds of Table 2 (note also that a < 0); the first three are sharp. But for 5 < d < 7, we do not know 0(Gd). For G5, we have only that 37 < 0 < 40. because G2 has no triangles, it is clear that 0(G2) = 8. A 13-coloring of the complement of G3 is shown in Table 5. Table 6 shows a covering of G4 by 22 cliques, the method for which we will explain shortly. That same method found 0(G5) < 40 (see Table 7). The values of 0frac in Table 2 arise from the vertex-transitive formula xfrac = nv/a on the complement, which becomes nv/w. The method of getting a minimal clique covering for G4 uses backtracking and the structure of the independence square (Table 3). As discussed, any clique cover for G4 has at least 22 cliques. One way to search for a cover using 22 cliques is to use twenty 12-cliques and two 8-cliques. So an initial goal was to search for 20 disjoint 12-cliques. The complete set of all 86,012 12-cliques was generated. We then tried backtracking on these to find a set of 20 pairwise disjoint cliques that could extend to a clique cover but the problem size proved unmanageable. Many search paths would get stuck after including only 16 of the 12-cliques. A second problem is that if after including the twenty 12-cliques, there is a row or column in the independence square that is not covered k times, then it is necessary to add at least k more cliques to complete the cover. So an auspicious selection of twenty 12-cliques should leave each row uncovered at most two times each. W. Jarnicki et al.: Properties, proved and conjectured, of Keller, Mycielski, and queen graphs 429 1 0233 1003 1020 1213 1221 1301 2101 3033 3113 3121 3312 3331 2 0013 0030 0200 1212 1220 1332 2012 2020 2100 3032 3202 3221 3 0100 0132 0212 0310 0333 1331 2010 2033 2131 2211 2223 3012 4 0223 0303 0331 1102 1121 1311 2123 2313 2330 3011 3103 3131 5 0101 1022 1103 1120 1302 1330 2222 3013 3021 3203 3220 3301 6 0001 0033 0113 1021 1211 1232 2000 2023 2213 3201 3233 3321 7 0111 0123 0203 0301 0322 1320 2001 2022 2120 2200 2232 3003 8 0302 1111 1132 1230 1310 1322 2030 3010 3022 3102 3200 3223 9 0003 0020 0122 0202 0230 1001 2113 2121 2201 2303 2320 3322 10 0011 0103 0131 0313 0330 1123 2002 2021 2203 2231 2323 3211 11 0110 1033 1112 1131 1313 1321 2233 3002 3030 3212 3231 3310 12 0012 0031 0133 0213 0221 1010 2102 2130 2210 2312 2331 3333 13 0220 1011 1023 1201 1222 1303 2103 3020 3101 3122 3300 3332 14 0000 0032 0120 0201 0222 1012 2110 2133 2212 2300 2332 3320 15 0231 1000 1032 1210 1233 1312 2112 3031 3110 3133 3311 3323 16 0121 0311 0332 1013 1101 1133 2221 2301 2333 3100 3123 3313 17 0002 0021 0211 1203 1231 1323 2003 2031 2111 3023 3213 3230 18 0232 0312 0320 1113 1130 1300 2132 2302 2321 3000 3112 3120 19 0010 0022 0102 1030 1200 1223 2011 2032 2202 3210 3222 3330 20 0130 0300 0323 1002 1110 1122 2230 2310 2322 3111 3132 3302 21 0112 0321 1100 1333 2122 2311 3130 3303 22 0023 0210 1031 1202 2013 2220 3001 3232 Table 6: A covering of the 256 vertices of G4 by 22 disjoint complete subgraphs. To attempt to deal with both of these problems, the search was restricted to only cliques that had certain subsets of the rows missing. After inspecting the subsets of rows that could be missing from one of the cliques, the following selection was made (where the rows are indexed by 0,1,..., 15. Group 1 Rows 0, 3, 12, and 15 are missing. Group 2 Rows 1, 2, 13, and 14 are missing. Group 3 Rows 4, 7, 8, and 11 are missing. Group 4 Rows 5, 6, 9, and 10 are missing. Backtracking on just these cliques led to several sets of twenty 12-cliques. A backtracking program was used to try to complete the clique cover, and this quickly led to a solution (most of the sets of 20 do not extend to a clique cover of size 22 but it did not take long to find one that did); see Table 6. The set of 20 that completed had 5 tuples from each group meaning that each row was used exactly 15 times (and was missing once). Similar ideas yielded the 44-clique for G5 (Table 7). It is well-known (see [6, Thm. 4.2]) that a clique in Gd can be used to create a clique twice as large in Gd+1 by making two copies of it, prefacing the first copy with the digit 0, adding 1 modulo 4 to each position of each tuple in the second copy, and then prefacing each tuple in the second copy with the symbol 2. The clique also can be doubled using digits 1 and 3 as the first digits instead of 0 and 2. To double a clique cover, start with each clique C. Double C using first digits 0 and 2. Then double the clique C again using 1 and 3 as the initial digits. The original clique cover used all the d-tuples exactly once. For first digit 0 and 1 it is easy to see that each tuple is used exactly once. Similarly for first digits 1 and 3, each tuple appears exactly once, because adding 11... 1 to every tuple of dimension d gives back the complete set of tuples in dimension d. This construction gives a clique §