Problem 1. Does there exists a polynomial-time algorithm which, given a neartriangulation G with the outer face bounded by a 4-cycle C and a 4-coloring ψ of C, correctly decides whether ψ extends to a 4-coloring of G?

Note that there exist infinitely many near-triangulations G with the outer face bounded by a 4-cycle C such that not every precoloring of C extends to a 4coloring of G; and we do not have any good guess at how the near-triangulations with this property could be described.

Nevertheless, we do have some information about the precoloring extension properties of plane near-triangulations. For a plane near-triangulation G with the outer face bounded by a cycle C, let n ⋆ G denote the function that to each 4-coloring ψ of C assigns the number of ways ψ extends to a 4-coloring of G; hence, ψ extends to a 4-coloring of G if and only if n ⋆ G (ψ) = 0. Suppose C = v 1 v 2 v 3 v 4 is a 4-cycle and ψ 1 , ψ 2 and ψ 3 are its 4-colorings such that ψ i (v j ) = j for i ∈ {1, 2, 3} and j ∈ {1, 2}, ψ 1 (v 3 ) = ψ 3 (v 3 ) = 1, ψ 2 (v 3 ) = 3, ψ 1 (v 4 ) = ψ 2 (v 4 ) = 2, and ψ 3 (v 4 ) = 4; see Figure 1. A standard Kempe chain argument shows that if n ⋆ G (ψ 1 ) = 0, then n ⋆ G (ψ 2 ) = 0 or n ⋆ G (ψ 3 ) = 0. Actually, much more information can be obtained along these lines, using the idea of Block-count reducibility [3,4] developed in connection with the attempts to prove the Four Color Theorem: Certain inequalities between linear combinations of n ⋆ G (ψ 1 ), n ⋆ G (ψ 2 ), and n ⋆ G (ψ 3 ) are satisfied for all near-triangulations G, or equivalently, the vector (n ⋆ G (ψ 1 ), n ⋆ G (ψ 2 ), n ⋆ G (ψ 3 )) is contained in a certain cone in R 3 . The main goal of this note is to present and motivate a conjecture regarding this cone in the case of near-triangulations with the outer face bounded by a 5-cycle; this conjecture strengthens the Four Color Theorem. We also provide evidence supporting this conjecture.

In order to describe the cone we alluded to in the introduction, we need a number of definitions, which we introduce in this section. It is easier to state the idea in the dual setting of 3-edge-colorings of cubic plane graphs, which is well-known to be equivalent to 4-coloring of plane triangulations [6].

Some graphs in this paper may have parallel edges or loops. We call two parallel edges a double edge and three parallel edges a triple edge.

Let G be a connected graph and let v be a vertex of G. A half-edge is (e, u), where e is an edge and u is one of its endpoints. If e = uv, when we say u is incident with (e, u) but it is not incident with (e, v). We consider each edge e = uv of G as consisting of two half-edges (e, u) and (e, v) even if e is a loop. Let ν be a bijection between the half-edges incident with v and {0, . . . , deg(v) -1} (so, if v is incident with a loop, each half of the loop is assigned a different number by ν). If all vertices of G other than v have degree three, we say that G = (G, v, ν) is a near-cubic graph. We say that G is a plane near-cubic graph if G is a plane graph and the half-edges incident with v are drawn around it in the clockwise cyclic order ν -1 (0), . . . , ν -1 (deg(v) -1). We define d( G) = deg(v).

A 3-edge-coloring of G is an assignment of colors 1, 2, and 3 to edges of G such that any two edges incident with a common vertex other than v have different colors. For an integer d ≥ 2, a function

. This parity condition is necessary, see Observation 2. We say that a 3-edge-coloring ϕ of G extends a d( G)-precoloring ψ if for any edge e incident with v and a half-edge h of e incident with v, we have ϕ(e) = ψ(ν(h)).

Let n G(ψ) denote the number of 3-edge-colorings of G which extend ψ. Via the theory of nowhere-zero flows [7], it is easy to establish the following correspondence between 4-colorings of near-triangulations and 3-edge-colorings in their duals. Recall n ⋆ G (ψ) denotes the number of 4-colorings of G which extend ψ.

Observation 3. Let G = (G, v, ν) be a plane near-cubic graph, and let G ⋆ be the dual of G drawn so that the outer face of G ⋆ corresponds to v. Suppose the outer face of G ⋆ is bounded by a cycle C. Then there exists a mapping f from 4-colorings of C to d( G)-precolorings such that • f maps exactly four distinct 4-colorings of C to each d( G)-precoloring, and

1 (i) and ν -1 2 (i) and connecting the other halfs of the edges. Note that G1 ⊕ G2 is a cubic graph, and if G1 and G2 are plane near-cubic graphs, then G1 ⊕ G2 is a cubic planar graph. Observe that the number of 3-edge-colorings of G1 ⊕ G2 is

where the sum goes over all deg(v 1 )-precolorings ψ. For any integer n ≥ 3, let Cn denote the plane near-cubic graph (W n , v, ν), where W n is the wheel with the central vertex v adjacent to all vertices of an n-cycle; see Figure 2.

The following definition of d-signature is will be used to capture the possible parities of 2-edge-colored cycles containing v in a 3-edge-coloring of G = (G, v, ν) distinguished by the half-edges contained in the cycles. In particular, parity will be s ∈ {-1, 1} and the pair of half-edges will be m. For an integer d ≥ 2, a d-signature is a set S of pairs (m, s), where m is an unordered pair of integers in {0, . . . , d -1} and s ∈ {-1, 1}, satisfying the following conditions:

(i) for any distinct (m 1 , s 1 ), (m 2 , s 2 ) ∈ S we have m 1 ∩ m 2 = ∅, and

(ii) S does not contain elements ({a, b}, s 1 ) and ({c, d}, s 2 ) such that a < c < b < d.

A d-precoloring ψ is compatible in (distinct) colors i, j ∈ {1, 2, 3} with a dsignature S if

• ψ -1 ({i, j}) = (m,s)∈S m, and

• for each ({a 1 , a 2 }, s) ∈ S, ψ(a 1 ) = ψ(a 2 ) holds if and only if s = -1.

Now, consider a 3-edge-coloring ϕ of a near-cubic graph G = (G, v, ν). Each vertex other than v is incident with edges of all three colors. Hence, for any distinct i, j ∈ {1, 2, 3}, the subgraph G ij of G consisting of edges of colors i or j is a union of pairwise edge-disjoint cycles, vertex-disjoint except for possible

Note that if G is plane, then the ij-Kempe chains do not cross and the ij-Kempe chain signature of ϕ satisfies the condition (ii); and thus σ ij (ϕ) is a d( G)-signature.

Let G = (G, v, ν) be a plane near-cubic graph and let ψ be a d( G)-precoloring. Suppose that ψ is compatible (in colors i, j ∈ {1, 2, 3}) with a d( G)-signature S. We define n G,S (ψ) as the number of 3-edge-colorings ϕ of G extending ψ such that σ ij (ϕ) = S. Note that swapping the colors i and j on any set of ij-Kempe chains of ϕ results in another 3-edge-coloring with the same ij-Kempe chain signature. Furthermore, clearly for any permutation π of colors, we have n G,S (ψ • π) = n G,S (ψ). This establishes bijections implying the following.

Hence, we can define an integer n G,S to be equal to n G,S (ψ) for an arbitrarily chosen d( G)-precoloring ψ compatible with S.

Let d ≥ 2 be an integer and let i, j ∈ {1, 2, 3} be distinct colors. For a d-precoloring ψ, let us define S ψ,ij as the set of d-signatures compatible with ψ in colors ij. Since every 3-edge-coloring of G has an ij-Kempe chain signature, we have

Let P d denote the set of all d-precolorings and S d the set of all d-signatures. We will work in the vector spaces R P d and R S d with coordinates corresponding to the d-precolorings and to the d-signatures, respectively. For each integer d ≥ 2, the coloring count cone B d is the set of all x ∈ R P d such that

• x(ψ) ≥ 0 for every d-precoloring ψ, and

• there exists y ∈ R S d such that y(S) ≥ 0 for every d-signature S, and x(ψ) = S∈S ψ,ij y(S) for every d-precoloring ψ and distinct colors i, j ∈ {1, 2, 3}.

Note that B d is indeed a cone, i.e., an unbounded polytope closed under linear combinations with non-negative coefficients. By (2), the vector of precoloring extension counts for any plane near-cubic graph belongs to the corresponding coloring count cone.

Theorem 5. For each plane near-cubic graph G, we have

Each cone is uniquely determined as the set of non-negative linear combinations of its rays. For d ∈ {2, 3, 4, 5}, the rays of B d are easy to enumerate by hand or using polytope-manipulation software such as Sage Math or the Parma Polyhedra Library (a program doing so for d = 5 can be found at http://lidicky.name/pub/4cone/). For a near-cubic graph G such that n G is not the zero function, let ray( G) denote the set of all non-negative multiples of n G. Graphs R2,1 , . . . , R5,12 used in the following lemma are depicted in Figure 3. Lemma 6. Refering to graphs in Figure 3: • the cone B 2 has exactly one ray equal to ray( R2,1 );

• the cone B 3 has exactly one ray equal to ray( R3,1 );

• the cone B 4 has exactly four rays equal to ray( R4,1 ), . . . , ray( R4,4 ); and

• the cone B 5 has exactly 12 rays equal to ray( R5,1 ), . . . , ray( R5,12 ).

Let us remark that B 6 has 208 rays; the direct method we employ is too slow to enumerate all rays for d ≥ 7 on current workstations.

3 The cone B 5 and the conjecture Note that while R5,1 , . . . , R5,11 are plane, R5,12 is not. Indeed, the following holds. Proof. Let us first prove that (a) implies (b). Consider a plane near-cubic graph G = (G, v, ν) such that n G ∈ ray( R5,12 ), and thus for some constant c ≥ 0, we have n G(ψ) = c • n R5,12 (ψ) for every 5-precoloring ψ. Observe that n R5,12 (ψ)n C5 (ψ) = 0 for every 5-precoloring ψ (since R5,12 ⊕ C5 is the Petersen graph, which is not 3-edge-colorable; see Figure 4), and thus the number of 3-edge-colorings of G ⊕ C5 using (1) is

Hence, the planar cubic graph G ⊕ C5 is not 3-edge-colorable. By (a), G ⊕ C5 has a bridge, and thus G has a bridge. But then a standard parity argument implies that G has no 3-edge-coloring, and thus n G is the zero function.

Next, let us prove that (b) implies (a). Suppose for a contradiction that (b) holds, but there exists a plane cubic 2-edge-connected graph that is not 3-edgecolorable, and let H be one with the smallest number of vertices. By Euler's formula and possible parallel edges, H has a face f of length 2 ≤ d ≤ 5; hence, R5,12 C5 0 0 1 1 4 4 2 2 3 3 R5,12 1 2 3 4 0 C5 Figure 4: R5,12 ⊕ C5 in two different drawings. we can write H = G ⊕ Cd for a plane near-cubic graph G. By Theorem 5, we have n G ∈ B d , and by Lemma 6, there exist non-negative real numbers

Observe there exists a plane near-cubic graph P with d -1 vertices such that G ⊕ P is 2-edge-connected. By the minimality of H, G ⊕ P is 3-edge-colorable, and in particular n G is not the zero function. By (b), n G is not a positive multiple of n R5,12 , and thus there exists an index k ≤ 11 such that c k > 0.

Observe that Rd,k ⊕ Cd is 3-edge-colorable, and thus there exists a d-precoloring ψ 0 such that n Rd,k (ψ 0 )n Cd (ψ 0 ) > 0. However, then the number of 3-edgecolorings of H is

This contradicts the assumption that H is not 3-edge-colorable.

Note that (a) from Lemma 7 is well-known to be equivalent to the Four Color Theorem [6], and thus indeed there is no plane near-cubic graph G with d( G) = 5 such that n G is not the zero function and n G ∈ ray( R5,12 ); and furthermore, a direct proof of this fact would imply the Four Color Theorem. Motivated by this observation (and experimental evidence), we propose the following conjecture, a strengthening of the Four Color Theorem. Let B ′ 5 denote the cone in R P d with rays ray( R5,1 ), . . . , ray( R5,11 ).

For i ∈ {0, . . . , 4}, let ψ 5,a i and ψ 5,b i denote the 5-precolorings whose values at j ∈ {0, . . . , 4} are defined by the following table; see also Figure 5. Notice that i is a rotating the coloring. (ji) mod 5 ψ 5,a i (j)

Note that each 5-precoloring is obtained from one of these ten by a permutation of colors. The cone B ′ 5 has exactly one facet which is not also a facet of B 5 , giving an equivalent formulation of Conjecture 8. In the rest of the note, we provide some evidence supporting Conjecture 8; in particular, we show there are no counterexamples to the conjecture for plane near-cubic graphs with less than 30 vertices.

In this section we present experimental evidence for the validity of Conjecture 8. Our goal is to show Corollary 20 stating that Conjecture 8 holds for graphs on at most 30 vertices. The main idea of our approach is to generate larger graphs G from smaller graphs by planarity preserving operations. One such is depicted in Figure 7. We will generate "all" possibilities for d( G) ≤ 7 and particular ones with d( G) = 8. We then argue that all graphs in at most 30 vertices can be generated this way.

We begin by stating a few more definitions. A vector x ∈ P d is invariant with respect to permutation of colors if all d-precolorings ψ and ψ ′ that only differ by a permutation of colors satisfy x(ψ) = x(ψ ′ ).

See Figure 6 for an illustration of the following definitions. The rotation by t of a d-precoloring ψ is the d-precoloring r t (ψ) such that r t (ψ) , c d-1 .

let r t (x) be defined as y ∈ R P d such that y(r t (ψ)) = x(ψ) for every d-precoloring ψ, and let f (x) be defined as z ∈ R P d such that z(f (ψ)) = x(ψ) for every d-precoloring ψ. A set K ⊆ R P d is closed under rotations and flips if we have x ∈ K if and only if f (x) ∈ K and r t (x) ∈ K for all t ∈ {0, 1, . . . , d -1}. For a near-cubic graph G = (G, v, ν) with deg(v) = d, let r t ( G) denote the near-cubic graph (G, v, ν 1 ), where ν -1 1 ((i+t) mod d) = ν -1 (i) for i ∈ {0, . . . , d-1}, and let f ( G) denote the near-cubic graph (G, v, ν 2 ), where ν -1 Let ψ 1 be a d 1 -precoloring and ψ 2 a d 2 -precoloring. For an integer k ≤ min(d 1 , d 2 ), we say that

where the sum is over all k-matching d 1 -precolorings ψ 1 and d 2 -precolorings ψ 2 . For near-cubic graphs G1

, where G is obtained from G 1 and G 2 by identifying v 1 with v 2 to a single vertex v and for i ∈ {0, 1, . . . , k -1} removing the half-edges ν -1 1 (d 1k + i) and ν -1 2 (d 2 -1i) and connecting the other halfs of the edges; and ν 7 for an illustration.

Observation 11. Let G1 and G2 be near-cubic graphs. For every integer k ∈ {0, . . . , min(d( G1 ), d( G2 ))}, we have By a computer-assisted enumeration, we verified the following claim. Lemma 12. There exists cones K d ⊆ R P d for d = 2, . . . , 8 such that the following claims hold. (a) K d = B d when d ≤ 4 and K 5 = B ′ 5 . (b) For all d ∈ {2, . . . , 8}, the elements of K d are invariant with respect to permutation of colors. (c) For d ∈ {2, . . . , 7}, the cone K d is closed under rotations and flips. (d) If 2 ≤ d 1 ≤ d 2 and d 1 + d 2 ≤ 7, then for all x 1 ∈ K d1 and x 2 ∈ K d2 we have γ 0 (x 1 , x 2 ) ∈ K d1+d2 . (e) If 2 ≤ d ≤ 5, then for all x ∈ K d we have γ 1

(h) For every x 1 ∈ K 8 and x 2 ∈ K 7 , we have γ 4 (x 1 , x 2 ) ∈ K 7 .

(i) For every

Proof. The proof and the program to verify the proof can be found at http:// lidicky.name/pub/4cone/. The cones are described by their rays, enumerated in the file. Cone K 6 has 102 rays, K 7 has 22605 rays, and K 8 has 4330 rays. It suffices to verify all the claims for x, x 1 , x 2 being the rays of the cones specified in the claims; the inclusion of the resulting vectors in the appropriate cone is certified by expressing them as a linear non-negative combination of the rays of the cone.

Parts (e) and (f) of Lemma 12 have the following corollary. Hence, Gv is connected (and the same argument as for disconnected Gv shows that no loop is incident with v). Consequently, v is not incident with a triple edge. If v is incident with a double edge, then we can by symmetry assume that G = γ 1 ( R3,1 , G1 ) for a plane near-cubic graph G1

. By the induction hypothesis, there exists a plane near-cubic graph G0 = (G 0 , v 0 , ν 0 ) with

and thus also of Gv, and

Hence, we can assume v is not incident with a double edge. Consequently, we can by symmetry assume that G = γ 2 ( R3,1 , G1 ) for a plane near-cubic graph G1 = (G 1 , v 1 , ν 1 ) with d( G1 ) = d + 1. By Lemma 12(f), since n G ∈ K d , we have n G1 ∈ K d+1 . By the induction hypothesis, there exists a plane near-cubic graph G0 = (G 0 , v 0 , ν 0 ) with

Hence, the claim of the lemma follows.

We will say that a plane near-cubic graph G = (G, v, ν) is extremal if d( G) = 7, n G ∈ K 7 , and there does not exist any plane near-cubic graph G0 = (G 0 , v 0 , ν)

, then by Lemma 13 there would exist a plane near-cubic graph G0 = (G 0 , v 0 , ν 0 ) such that d( G0 ) = 7, n G0 ∈ K 7 and G 0v 0 is an induced subgraph of G ′v ′ . However, then G 0v 0 would be a proper minor of Gv, contradicting the assumption that G is extremal.

Next, let us explore consequences of part (g) of Lemma 12.

Lemma 15. If G = (G, v, ν) is an extremal plane near-cubic graph, then v is not incident with loops or parallel edges and Gv is 2-edge-connected.

Proof. Analogously to the proof of Lemma 13, if v were incident with a loop or a parallel edge or if Gv were not 2-edge-connected, we would have G = γ c ( G1 , G2 ) for plane near-cubic graphs G1 and G2 such that 2 ≤ d( G1 ) ≤ d( G2 ), d( G1 ) + d( G2 ) = 7 + 2c, and c ≤ 1; in particular, d( G2 ) ≤ 7 and d( G1 ) ≤ ⌊(7 + 2c)/2⌋ ≤ 4. By Lemma 14, we have n Gi ∈ K d( Gi) for i ∈ {1, 2}. By Lemma 12(g), we conclude n G ∈ K 7 , which is a contradiction. Suppose A and B form a partition of the vertex set of a graph H, and let S be the set of edges of H with one end in A and the other end in B. In this situation, we say S is an edge cut of H with sides A and B.

Lemma 16. If G = (G, v, ν) is an extremal plane near-cubic graph, then Gv does not contain an edge cut S such that v has at least |S| neighbors in each side of the cut.

Proof. Suppose for a contradiction Gv contains such an edge cut S of size c, and thus G = γ c ( G1 , G2 ) for plane near-cubic graphs G1 and G2 such that 2c ≤ d( G1 ) ≤ d( G2 ) and d( G1 ) + d( G2 ) = 7 + 2c. Since v has 7 neighbors and at least c of them are contained in each of the sides of the cut, we have c ≤ 3. Note that d( G2 ) ≤ 7 and d( G1 ) ≤ ⌊(7 + 2c)/2⌋ ≤ 6. By Lemma 14, we have n Gi ∈ K d( Gi) for i ∈ {1, 2}. By Lemma 12(g), we conclude n G ∈ K 7 , which is a contradiction.

An edge cut S of size at most five in a near-cubic graph G = (G, v, ν) is essential if the side of S containing v contains at least one other vertex and the other side B of S induces neither a tree nor a 5-cycle.

Lemma 17. If G = (G, v, ν) is an extremal plane near-cubic graph, then G does not contain an essential edge cut S of size at most five.

Proof. Suppose for a contradiction that G contains an essential edge-cut S of size k ≤ 5, and choose one with minimum k, and subject to that one for which the side B not containing v is minimal. We claim G[B] is 2-edge-connected. Otherwise, B is a disjoint union of non-empty sets B 1 and B 2 , where G contains r ≤ 1 edges with one end in B 1 and the other end in B 2 . For i ∈ {1, 2}, let S i denote the set of edges of G with exactly one end in B i . Since G is extremal, n G ∈ K 7 is not identically zero, and thus G is 2-edge-connected, implying Observe that all edges of S are drawn inside f . Otherwise, the set S ′ of edges of S drawn inside C forms an edge cut of order smaller than k and by the minimality of k, its side B ′ B induces a tree or a 5-cycle; this is not possible, since G[B] is 2-edge connected and not a tree.

Let Gc be the plane near-cubic graph obtained from G by contracting the side of the cut containing v to a single vertex. By Lemma 14, we have

where i ≤ 11 if k = 5 and the coefficients c i are non-negative. Let Gi = (G i , v i , ν i ) denote the plane near-cubic graph obtained from G by replacing the side of the cut S not containing v by Rk,i . Note that n G = i c i n Gi , and since K 7 is a cone and n G ∈ K 7 , there exists i such that n Gi ∈ K 7 . Because B contains the cycle C S and all edges of S are incident with vertices of C S , we see G iv i is a proper minor of Gv, contradicting the extremality of G.

In Lemma 15, we argued that if G = (G, v, ν) is an extremal plane nearcubic graph, then Gv is 2-edge-connected, and thus its face containing v is bounded by a cycle C. Let us now argue that the graph stays 2-edge-connected after removing V (C) as well.

denote the set of faces of G ′ separated from v by C ′ and let Y (G ′ ) denote the set of faces of G ′ separated from v by C but not by C ′ . See Figure 8(a) for an example. For i ∈ {1, . . . , 7}, we say that a face f ∈ X(G ′ ) sees P i if there exists a face f ′ ∈ Y (G ′ ) such that f ′ is incident with an edge of P i and the boundaries of f and f ′ share at least one edge.

If for some i ∈ {1, . . . , 7}, some face of X(G) saw P i , P i+2 , and P i+4 (with indices taken cyclically) then G = γ 4 (r 2 (γ 2 ( G1 , G2 )), G3 ) for plane near-cubic graphs G1 , G2 , and G3 with d( G1 ) = d( G2 ) = 6 and d( G3 ) = 7 (see Figure 8(b)). Lemma 14 would imply n Gj ∈ K d( Gj ) for j ∈ {1, 2, 3}, and by Lemma 12(h) and (i), we would have n G ∈ K 7 , which is a contradiction. Hence, no face of X(G) sees P i , P i+2 , and P i+4 .

( • b 1 ≥ 8 and b 3 ≥ 3, or • b 3 ≥ 6, or • b 3 ≥ 4 and b 4 ≥ 1. Hence 3b 1 + 3b 2 + 2b 3 + b 4 ≥ 30, and thus G has at least 44 edges. Consequently, |V (G)| ≥ (2|E(G)| -4)/3 ≥ 28. As a consequence, this verifies Conjecture 8 for small graphs. Corollary 20. Conjecture 8 holds for all plane near-cubic graphs with less than 30 vertices. Proof. Let G = (G, v, ν) be a counterexample to Conjecture 8, and in particular n G ∈ B ′ 5 = K 5 . By Lemma 13, there exists a plane near-cubic graph G0 = (G 0 , v 0 , ν 0 ) such that d( G0 ) = 7, n G0 ∈ K 7 , and |V (G 0 )| ≤ |V (G)| -2. Hence, there exists an extremal plane near-cubic graph G1 = (G 1 , v 1 , ν 1 ) such that |V (G 1 )| ≤ |V (G 0 )|. By Lemma 19, we have |V (G 1 )| ≥ 28, and thus |V (G)| ≥ 30.

Note that the analysis at the end of the proof of Lemma 19 can be improved. By a computer-assisted enumeration, one can show that to ensure that (3) holds, Gv must contain one of 38 specific graphs as a minor; the smallest are depicted in Figure 9. Hence, every counterexample to Conjecture 8 must