List edge colourings of some 1-factorable multigraphs

M. N. Ellingham^{1} Department of Mathematics, 1326 Stevenson Center Vanderbilt University, Nashville, TN 37240, U. S. A.

                              mne@math.vanderbilt.edu

Luis Goddyn^{2} Department of Mathematics and Statistics Simon Fraser University, Burnaby, B. C., V5A 1S6, Canada

                                goddyn@math.sfu.ca

Abstract

The List Edge Colouring Conjecture asserts that, given any multigraph G with chromatic index k and any set system {S_{e} : e ∈ E(G)} with each |S_{e}| = k, we can choose elements s_{e} ∈ S_{e} such that s_{e} ≠ s_{f} whenever e and f are adjacent edges. Using a technique of Alon and Tarsi which involves the graph monomial ∏{x_{u} − x_{v} : uv ∈ E} of an oriented graph, we verify this conjecture for certain families of 1-factorable multigraphs, including 1-factorable planar graphs.

Keywords: list edge colouring, choosability, 1-factorization, graph polynomial, graph monomial, planar graphs, regular graphs.

AMS Classification numbers: 05C15, (05C70, 05C10).

1 Introduction

Let G = (V, E) be a graph (with multiple edges allowed). A proper (vertex) colouring of G is a function on V for which adjacent vertices receive distinct values. A proper k-colouring is a proper colouring whose range is a subset of [k] := {0, 1, …, k−1}. With this definition, two distinct proper k-colourings of G may induce the same partition of V (G). A graph is k-colourable if it has a proper k-colouring. The following concept was introduced by Erdös, Rubin and Taylor [5]. Let a : V (G) → {1, 2, …}. We say that G is a-choosable or a-list colourable if for every set system {S_{v} : v ∈ V } such that |S_{v}| = a(v), there is a proper colouring c such that c(v) ∈ S_{v} for v ∈ V (G). In case a is the constant function a(v) ≡ k, we say that G is k-choosable. The terms k-edge colourable, a-edge choosable and k-edge choosable are defined in an analogous way. If a graph is k-choosable, then it is k-colourable, but not conversely, as shown by K_{3,3} which is not 2-choosable. In contrast, we have the following.

Conjecture 1.1 (List Edge Colouring Conjecture) If G is a k-edge colourable multigraph, then G is k-edge choosable.

This conjecture seems to have been arrived at independently by several people. It has been verified for the class of bipartite graphs [7], and also for complete graphs of odd order [8]. An excellent survey appears in [1]. Further results and historical comments may be found in [3, 4]. Our main result verifies this conjecture for a class of planar graphs.

Theorem 1.2 If G is a d-regular d-edge colourable planar multigraph, then G is d-edge choosable.

The Four Colour Theorem is equivalent to the statement that every 2-connected 3-regular planar graph is 3-edge colourable. Theorem 1.2 therefore implies that the Four Colour Theorem is equivalent to the statement that every 2-connected 3-regular planar graph is 3-edge choosable. This was observed independently by F. Jaeger and M. Tarsi [personal communication]. For d ≥ 4, the question of which d-regular planar multigraphs are d-edge colourable has not yet been resolved. Seymour [15] and others have proposed conjectures that would imply that any d-edge connected d-regular planar multigraph of even order is d-edge colourable, and hence, by Theorem 1.2, d-edge choosable.

1Supported by the University Research Council of Vanderbilt University and NSERC Canada.

2Supported by NSERC Canada.

Our main tool is a result of Alon and Tarsi [2] which relates choosablility to coefficients in a certain polynomial. Let D be an orientation of G. The graph monomial of G is the homogeneous polynomial ϵ(G) with variables {x_{v} : v ∈ V (G)} and defined by

ϵ(G) = ∏_{uv∈E(D)}(x_{u} − x_{v}).

(Some authors call ϵ(G) the graph polynomial, but we abandon this overused term in favour of that used by Sabidussi [13].) As we have defined it, ϵ(G) depends on a particular orientation D of G; however changing the orientation multiplies ϵ(G) by ±1, so ϵ(G) is unique up to sign. The graph monomial was first used by Petersen [12]; indeed Petersen gave order, degree and factor their graph theoretical meanings by reference to ϵ(G). Scheim [14] used ϵ(G) to prove some results about 3-edge colourings of 3-regular planar graphs; our Theorem 1.2 extends one of his results. Li and Li [10] mention ϵ(G) in the context of determining the independence number of G.

Theorem 1.3 (Alon and Tarsi [2]) Let a : V (G) → {1, 2, …}. If the coefficient of ∏_{v∈V (G)} x_{v}^{a(v)−1} in ϵ(G) is nonzero, then G is a-choosable.

Scheim’s paper [14] contains much of the reasoning needed to prove this theorem; however, he was working before the introduction of the idea of list colourings, and did not state his results in full generality. Alon and Tarsi [2] give combinatorial interpretations of the coefficients of ϵ(G), and use Theorem 1.3 to investigate the (vertex) choosability of planar graphs and bipartite graphs. Fleischner and Stiebitz [6] use Alon and Tarsi’s results to solve a conjecture of Erdös regarding the 3-vertex colourability of certain 4-regular graphs. Penrose [11] states the case d = 3 of Theorem 3.1 in terms of “abstract tensor systems”.

2 Interpreting the Coefficient

In order to study edge choosability one applies Theorem 1.3 to line graphs. The line graph L(G) of a multigraph G has V (L(G)) = E(G) with an edge joining e to f in L(G) for each common endpoint that e and f have in G. Thus, every pair of parallel edges in G is joined by two edges in L(G). For regular G, the coefficient of ϵ(L(G)) which is of interest has several nice combinatorial interpretations, some of which are implicit in [2] and explicitly described by N. Alon in the preamble to Proposition 3.8 of [1].

From here on, G is a d-regular multigraph. Let ξ(G) denote the coefficient of ∏_{e∈E(G)} x_{e}^{d−1} in ϵ(L(G)). If ξ(G) ≠ 0, then G is d-edge choosable, and thus the List Edge Colouring Conjecture holds true for G.

The set of edges δ(v) incident with each vertex v of G can be ordered with a star labelling at v, a bijection π_{v} : δ(v) → [d]. A global star labelling is a set π = {π_{v} : v ∈ V (G)}. We assume that G comes with a fixed global star labelling ρ = ρ(G) = {ρ_{v}}, called the reference labelling of G, with which other star labellings will be compared. In particular, the sign of a star labelling π_{v} (relative to ρ) is the sign of the permutation π_{v} ∘ ρ_{v}^{−1}, and is denoted sign_{ρ}(π_{v}), or sometimes just sign(π_{v}). The sign of a global star labelling π is defined as sign(π) = ∏_{v∈V (G)} sign(π_{v}).

Star labellings allow us to assign signs to other combinatorial objects in G. A k-factor in G is a k-regular spanning subgraph of G. Let p = ⌈d/2⌉. An ordered (near) 2-factorization of G is an ordered partition F = (F_{0}, F_{1}, …, F_{p−1}) of E(G), where each F_{i} is a 2-factor, unless d is odd, in which case F_{p−1} is a 1-factor (hence the word “near”). An orientation Φ of F is an orientation of G so that each F_{i} becomes a union Φ_{i} of directed circuits, except that when d is odd Φ_{p−1} = F_{p−1} remains an unoriented 1-factor. Let OOB2F(G) denote the set of oriented ordered (near) 2-factorizations of G in which each 2-factor is bipartite, i.e. a union of even circuits. For each Φ ∈ OOB2F(G), there is an associated global star labelling π: given uv ∈ Φ_{i} oriented from u to v, we set π_{u}(uv) = i and π_{v}(uv) = d − 1 − i, or if d is odd and uv ∈ Φ_{p−1} then π_{u}(uv) = π_{v}(uv) = (d − 1)/2. We define sign(Φ) = sign_{ρ}(Φ) to be sign(π). As shown in [1],

ξ(G) = ± ∑_{Φ∈OOB2F(G)} sign(Φ).  (1)

Let B2F(G) denote the set of unordered and unoriented bipartite (near) 2-factorizations of G. For any F ∈ B2F(G), we can define sign(F) = sign_{ρ}(F) to be sign(Φ) for any orientation Φ of any ordering of F. All such Φ have the same sign, because reversing the orientation of an even circuit changes the sign at an even number of vertices, and swapping two 2-factors swaps two pairs of edges at each vertex. If ω(F) is the total number of circuits in all of the 2-factors in F, then there are 2^{ω(F)} orientations of each of the ⌊d/2⌋! orderings of F, so that (1) may be rewritten as

ξ(G) = ± ⌊d/2⌋! ∑_{F ∈B2F(G)} sign(F) 2^{ω(F)}.  (2)

The coefficient ξ(G) may also be interpreted in terms of edge colourings of G. Let EC_{d}(G) denote the set of proper d-edge colourings c : E(G) → [d]. Each c ∈ EC_{d}(G) induces a global star labelling τ = τ(c) where for each edge e = uv, τ_{u}(e) = τ_{v}(e) = c(e). We define the sign of c (with respect to ρ(G)) by sign(c) = sign(τ(c)). As explained in [1], there is a bijection between OOB2F(G) and EC_{d}(G) which preserves all or reverses all signs, giving

ξ(G) = ± ∑_{c∈EC_{d}(G)} sign(c).  (3)

Let 1F(G) denote the set of unordered 1-factorizations of G. Each f ∈ 1F(G) corresponds to an equivalence class of d! edge colourings in EC_{d}(G) under permutations of the colours [d]. As interchanging two colours in c introduces exactly |V (G)| transpositions in τ(c), equivalent colourings in EC_{d}(G) have equal sign. Thus a sign function is well defined on 1F(G).

ξ(G) = ± d! ∑_{f∈1F(G)} sign(f)  (4)

There is a coarser equivalence relation on EC_{d}(G) on whose parts a sign function can be defined. An elementary Kempe recolouring of c ∈ EC_{d}(G) exchanges the colours i and j on the edges of a single component circuit of the 2-factor c^{−1}(i) ∪ c^{−1}(j), for some distinct i, j ∈ [d]. Two elements of EC_{d}(G) (or 1F(G)) are Kempe equivalent if one can be obtained from the other by a sequence of elementary Kempe recolourings. Let KE(G) denote the set of Kempe (equivalence) classes of proper d-edge colourings of G. As with 1-factorizations, Kempe equivalent colourings have the same sign, and the sign of a Kempe class is well defined.

ξ(G) = ± ∑_{κ∈KE(G)} sign(κ) |κ|  (5)

We summarize with a list of sufficient conditions for a graph to be d-edge choosable.

Theorem 2.1 Let G be a d-regular multigraph. Suppose that at least one of the following holds.

(i) G has an odd number of distinct 1-factorizations,

(ii) G is 1-factorable and any two 1-factorizations are Kempe equivalent,

(iii) G is 1-factorable and any two 1-factorizations have the same sign, or

(iv) the number of F ∈ B2F(G) which minimize the total number ω(F) of circuits in all of the 2-factors in F is odd.

Then ξ(G) ≠ 0, and as a consequence G is d-edge choosable.

Proof. Claims (i) and (iii) follow immediately from (4), while (ii) follows from (5). If (iv) holds then the sum in (2) is non-zero modulo 2^{ω_{0}+1}, where ω_{0} = min{ω(F) : F ∈ B2F(G)}.

Note that condition (ii) implies condition (iii). We illustrate with some examples of d-regular graphs which are d-edge choosable by Theorem 2.1. The skeleton of the 3-cube has four distinct 1-factoriz-ations, but they are all Kempe equivalent; thus (ii) applies, although (i) does not. The generalized Petersen graph P (9, 2) has a unique 1-factorization [16], and so (i) and (ii) both apply. Larger generalized Petersen graphs P (6k + 3, 2), k ≥ 2, are not uniquely 1-factorable, but have exactly three Hamilton circuits [16]. Thus ω(F) is minimum (equal to 1) for exactly three F ∈ B2F(G). These provide an examples of (iv) whereas (i), (ii) and (iii) may not hold. The 8-vertex Möbius ladder (which may be thought of as an octagon with all four long diagonals added) has exactly three 1-fac-torizations, and they are all Kempe equivalent; therefore (i) and (ii) both apply. The skeleton of the dodecahedron has exactly ten 1-factorizations, each in its own Kempe class and all of the same sign; thus (iii) applies. The even complete graphs K_{2r} satisfy (iii) for r ≤ 3, but not for r ≥ 4. It appears likely that ξ(K_{2r}) is never zero (we have verified this electronically for r ≤ 5), though this is probably a difficult problem. It is not even known whether the List Colouring Conjecture holds for K_{2r}. Similarly, we expect that ξ(K_{2r,2r}) is never zero (as has been verified for r ≤ 5 by J. Janssen [private communication]), although (iii) holds only for r ≤ 2.

In the next section we show that all 1-factorizations of a regular planar multigraph have the same sign. In contrast, K_{3,3} has exactly one 1-factorization of each sign, thus ξ(K_{3,3}) = 0. (Even so, K_{3,3} is 3-edge choosable as it is bipartite [7].) This is a special case of the situation for K_{d,d} with d ≥ 3 odd, which is discussed in [2]. More generally we have the following.

Proposition 2.2 If G is d-regular, with d odd, and there exist distinct vertices v, v′ with identical neighbourhoods, then ξ(G) = 0.

Proof. We consider the involution on EC_{d}(G) which interchanges the colours of vw and v′w, for each neighbour w of v. This involution is fixed-point free and, as d is odd, is sign-reversing. Thus by (3), ξ(G) = 0.

We briefly describe two operations which can be used to produce regular multigraphs G with ξ(G) = 0. Let G_{0} and G_{1} be disjoint d-regular multigraphs of even order, and let v_{i} ∈ V (G_{i}) and e_{i} ∈ E(G_{i}), i = 0, 1. We form a new d-regular multigraph H from (G_{0} − v_{0}) ∪ (G_{1} − v_{1}) by adding d new edges, each joining a neighbour of v_{0} to a neighbour of v_{1}. We also form a new d-regular multigraph K from (G_{0} − e_{0}) ∪ (G_{1} − e_{1}) by adding two new edges, each joining an endpoint of e_{0} to an endpoint of e_{1}. Using (3), one can show that ξ(H) = ±ξ(G_{0})ξ(G_{1})/d! and that ξ(K) = ±ξ(G_{0})ξ(G_{1})/d. Thus ξ(H) = ξ(K) = 0 provided that ξ(G_{0}) = 0. Pavol Gvozdjak (personal communication) has found a Hamiltonian cubic graph G with xi(G) = 0, but which does not arise from Proposition 2.2 nor either of these two operations. We do not know whether this graph is 3-edge colourable.

3 Regular planar multigraphs

In this section we prove Theorem 1.2 by showing the following.

Theorem 3.1 Let G be a d-regular planar multigraph, d ≥ 1. Then all 1-factorizations of G have the same sign. Hence |ξ(G)| is precisely the number of proper d-edge colourings of G.

The case d = 3 of this theorem was proved by Scheim [14], and can also be deduced from a result of Vigneron [17] (see also Jaeger [9]) together with observations of Alon and Tarsi [2] relating the coefficients of ϵ(G) to eulerian orientations of G. We leave as unsolved the problem of determining which graphs satisfy the conclusion of Theorem 3.1.

Roughly, we prove this theorem by giving a ‘geometric’ interpretation of sign(Φ) in (1), and then using the topology of the plane to deduce that this sign is always positive. We use terminology and notation from Section 2. Let G be a d-regular graph embedded on an orientable surface. For v ∈ V (G), a star labelling π_{v} is said to be clockwise if the edges are labelled in clockwise ascending order around v. A global star labelling π = {π_{v}} of G is clockwise if each of its members is clockwise. From here on we assume the reference labelling ρ(G) to be clockwise. Let Φ = (Φ_{0}, …, Φ_{p−1}) ∈ OOB2F(G) and let v be a vertex of G. For Φ_{i} ∈ Φ we denote by Φ_{i}(v) the connected component of Φ_{i} which contains v; thus Φ_{i}(v) is either an edge or a directed circuit. Two oriented 2-factors Φ_{i}, Φ_{j} ∈ Φ are said to cross at v if the circuits Φ_{i}(v), Φ_{j}(v) geometrically cross at v. We say that an edge e ∈ δ(v)\E(Φ_{i}) lies to the right of Φ_{i} (at v) if e lies geometrically on the right as Φ_{i}(v) is traversed through v. Similarly, if v lies on the boundary of a face R of the embedding, then R is to the left of Φ_{i} (at v) if R lies geometrically on the left as Φ_{i}(v) is traversed through v. It is important to note that the terms ‘cross’ and ‘to the left/right’ can equally well (though more cumbersomely) be defined purely in terms of Φ and ρ(G), without reference to any embedding of G. For example, a face R is specified by a pair of edges in δ(v) having consecutive ρ_{v}-labels (modulo d); two 2-factors Φ_{i} and Φ_{j} cross at v if some cyclic rotation of the sequence ρ_{v} ∘ π_{v}^{−1}(i), ρ_{v} ∘ π_{v}^{−1}(j), ρ_{v} ∘ π_{v}^{−1}(d − 1 − i), ρ_{v} ∘ π_{v}^{−1}(d − 1 − j) is monotone, where π is the global star labelling associated with Φ.

We define three invariants which determine the sign of Φ (relative to ρ(G)). Let v ∈ V (G). We denote by x(Φ, v) the number of unordered pairs of 2-factors in Φ which cross at v. If d ≥ 1 is odd, then we define the root edge e_{v} to be the edge Φ_{p−1}(v); we let r(Φ, v) denote the number of oriented 2-factors Φ_{i} ∈ Φ for which e_{v} lies to the right of Φ_{i} at v. If d ≥ 2 is even, then we define the root face R_{v} to be the face specified by the ρ_{v}-labels 0 and d − 1; we let l(Φ, v) denote the number of oriented 2-factors Φ_{i} ∈ Φ for which R_{v} lies to the left of Φ_{i} at v. Finally, we set x(Φ) := ∑_{v∈V (G)} x(Φ, v), r(Φ) := ∑_{v∈V (G)} r(Φ, v), and l(Φ) := ∑_{v∈V (G)} l(Φ, v).

Lemma 3.2 Let G be a d-regular multigraph with reference labelling ρ. For any oriented ordered (near) 2-factorization Φ of G we have sign(Φ) = (−1)^{x(Φ)+r(Φ)} or sign(Φ) = (−1)^{x(Φ)+l(Φ)} according to whether d is odd or even.

Proof. Given any star labelling π_{v}, let Φ(v) denote the oriented ordered partion of δ(v) whose ith part is the directed path with edges π_{v}^{−1}(d − 1 − i) followed by π_{v}^{−1}(i), except that when d is odd the (p − 1)th part is the unoriented root edge e_{v} = π_{v}^{−1}(p − 1). In general, x(Φ, v) equals the number of pairs of paths in Φ(v) which cross, and r(Φ, v) (l(Φ, v)) is the number of such paths for which e_{v} (R_{v}) lies to the right (left).

Let π be the global star labelling associated with Φ. For each v, Φ(v) is just the restriction of Φ to δ(v). A ρ-consecutive transposition of π_{v} is any transposition which exchanges the π_{v}-labels on any two edges in δ(v) whose ρ_{v}-labels differ by exactly one. The sign of π_{v} is determined by the length of a sequence S of such transpositions which transforms π_{v} into ρ_{v}. In case d is odd, a ρ-consecutive transposition of π_{v} corresponds to a modification of Φ(v) which does exactly one of two things. First, it may cross or uncross exactly one pair of dipaths in Φ(v). Second, it may transfer e_{v} from one side of exactly one such dipath to its other side. By definition, if π_{v} = ρ_{v}, then x(Φ, v) = r(Φ, v) = 0. Thus x(Φ, v)+r(Φ, v) is congruent to the number of transpositions in S (modulo 2), so sign(π_{v}) = (−1)^{x(Φ,v)+r(Φ,v)}. Thus sign(Φ) = ∏_{v∈V (G)}(−1)^{x(Φ,v)+r(Φ,v)} = (−1)^{x(Φ)+r(Φ)}. The d-even case is exactly analogous, writing l and R_{v} in place of r and e_{v}.

We remark here on an essential difference between the d-odd and d-even cases. The root edge e_{v} is determined by Φ whereas the root face R_{v} is defined by ρ(G). There appears to be no way of resolving this dichotomy.

A plane graph is a specific embedding of a planar graph in the plane. To prove Theorem 3.1 it suffices, by (1), to show that x(Φ), r(Φ) and l(Φ) are even, for any Φ ∈ OOB2F(G), whenever G is plane and ρ(G) is clockwise. This (essentially) is proved in the next three lemmas.

Lemma 3.3 Let G be a plane d-regular multigraph with a clockwise reference labelling ρ. Then x(Φ) is even for any oriented ordered (near) 2-factorization Φ of G.

Proof. Let x_{ij} denote the number of vertices at which two oriented 2-factors Φ_{i}, Φ_{j} ∈ Φ cross. As any two edge-disjoint circuits in the plane geometrically cross an even number of times, each x_{ij} is even and thus x(Φ) = ∑_{ij} x_{ij} is even.

In contrast to x(Φ), both r(Φ) and l(Φ) depend on the particular orientation Φ of the underlying (near) 2-factorization F. However, their parities are not affected by reorientation, provided that each of the 2-factors in F is bipartite. In case d is odd, we use the following simple observation whose proof is omitted.

Proposition 3.4 Let G be a plane 3-regular multigraph, and let C be a circuit of G. Let i be the number of vertices of C incident with an edge inside C, and j the number of vertices of G inside C. Then i ≡ j (mod 2).

Lemma 3.5 Let G be a d-regular plane multigraph, where d ≥ 1 is odd, and suppose that ρ(G) is clockwise. Then r(Φ) is even, for any oriented ordered bipartite near 2-factorization Φ of G.

Proof. For 0 ≤ i ≤ p − 2, let r_{i} be the number of vertices v for which the root edge e_{v} is to the right of the oriented 2-factor Φ_{i} ∈ Φ. As r(Φ) = ∑_{i=0}^{p−2} r_{i}, it suffices to show that each r_{i} is even. For each i we argue as follows. We may assume that each circuit C in Φ_{i} is oriented clockwise so that ‘to the right of Φ_{i}’ is equivalent to ‘inside C’. For any circuit C in Φ_{i}, the vertices of G inside C are the vertices of a union of even circuits in Φ_{i}. Thus an even number of vertices of G lie inside C. Applying Proposition 3.4 to the (undirected) 3-regular subgraph of G induced by the edges in Φ_{i} ∪ Φ_{p−1}, there are an even number of vertices v in C for which e_{v} lies inside of C. As Φ_{i} is a disjoint union of circuits C, r_{i} is even as required.

For the d-even case, we need some preliminary definitions. Let G be a plane graph, and C a circuit in G. We say that C surrounds a vertex v (or face R) if v (or R) is contained within the bounded region of ^{2} − C. If H is a 2-factor of G and v is a vertex of G, let s(v, H) be the number of component circuits in H that surround v; define s(R, H) similarly for a face R. Suppose G is a d-regular plane multigraph, where d = 2p is even. Then the plane dual of G is bipartite, and we can properly 2-face-colour G, using colours 0 and 1, so that the outer face is coloured 0. If G has a 2-factorization F = {F_{0}, F_{1}, …, F_{p−1}}, then it is not difficult to see that every face R receives the colour obtained by reducing modulo 2 the sum s(R, F_{0}) + s(R, F_{1}) + … + s(R, F_{p−1}). We say that the reference labelling ρ(G) is 0-consistent if it is clockwise and each root face R_{v}, v ∈ V (G) is coloured 0.

Lemma 3.6 Let G be a d-regular plane multigraph, where d ≥ 2 is even, and suppose that ρ(G) is 0-consistent. Then l(Φ) is even, for any oriented ordered bipartite 2-factorization Φ of G.

Proof. We may assume that each component circuit C in Φ_{i} is oriented anticlockwise so that ‘to the left of Φ_{i}’ is equivalent to ‘inside C’. For 0 ≤ i ≤ p − 1 and for each vertex v, let l_{i}(v) equal 1 if R_{v} lies inside the circuit Φ_{i}(v), and 0 otherwise. For v ∈ V (G) we consider the colour of R_{v}, which is the modulo 2 reduction of ∑_{i=0}^{p−1} s(R_{v}, Φ_{i}), and which is also 0, because ρ is 0-consistent. For each i, s(R_{v}, Φ_{i}) = s(v, Φ_{i}) + l_{i}(v). Therefore, working modulo 2, the colour of R_{v} is

0 ≡ ∑_{i=0}^{p−1} s(v, Φ_{i}) + ∑_{i=0}^{p−1} l_{i}(v)

which implies

∑_{i=0}^{p−1} l_{i}(v) ≡ ∑_{i=0}^{p−1} s(v, Φ_{i}).

Therefore,

l(Φ) = ∑_{v∈V (G)} ∑_{i=0}^{p−1} l_{i}(v)

≡ ∑_{i=0}^{p−1} ∑_{v∈V (G)} s(v, Φ_{i}).

Since each component circuit C of each Φ_{i} has an even number of vertices, and s(v, Φ_{i}) is constant for all vertices of C, each sum ∑_{v∈V (G)} s(v, Φ_{i}) is even, and so l(Φ) is also even, as required.

Acknowledgments

The authors wish to thank Noga Alon, Roland Häggkvist and Jarik Nešetril for useful discussions.

References

[1] N. Alon, Restricted colorings of graphs, in “Surveys in Combinatorics”, Proc. 14^{th} British Combinatorial Conference, London Mathematical Society Lecture Notes Series 187, edited by K. Walker, Cambridge University Press, 1993, 1-33.

[2] N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), 125–134.

[3] B. Bollobás and H. R. Hind, A new upper bound for the list chromatic number, Discrete Math. 74 (1989) 65–75.

[4] Amanda Chetwynd and Roland Häggkvist, A note on list-colorings, J. Graph Theory 13 (1989) 87–95.

[5] P. Erdös, A. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979) 125–157.

[6] H. Fleischner and M. Stiebitz, A solution to a colouring problem of P. Erdös, Discrete Math. 101 (1992), 39–48.

[7] F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B 63 (1995), 153–159.

[8] R. Häggkvist and J. Janssen, New bounds on the list-chromatic index of the complete graph, submitted.

[9] F. Jaeger, On the Penrose number of cubic diagrams, Discrete Math. 74 (1989) 85–97.

[10] S.-Y. R. Li and W.-C. W. Li, Independence numbers of graphs and generators of ideals, Combinatorica 1 (1981) 55–61.

[11] Roger Penrose, Applications of negative dimensional tensors, in “Combinatorial Mathematics and its Applications” Proc. Conf, Oxford, 1969, Academic Press, London, 1971, 221-244.

[12] Julius Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891) 193–220.

[13] G. Sabidussi, Binary invariants and orientations of graphs, Discrete Math. 101 (1992), 251–277.

[14] David E. Scheim, The number of edge 3-colorings of a planar cubic graph as a permanent, Discrete Math. 8 (1974) 377–382.

[15] P. D. Seymour, Some unsolved problems on one-factorizations of graphs, Graph Theory and Related Topics, edited by J. A. Bondy and U. S. R. Murty, Academic Press (1979) 367–368.

[16] Andrew Thomason, Cubic graphs with three hamiltonian cycles are not always uniquely edge colourable, J. Graph Theory 6 (1982) 219–221.

[17] L. Vigneron, Remarques sur les réseaux cubiques de classe 3 associés au problème des quatre couleurs, C. R. Acad. Sc. Paris 223 (1946), 770-772.