A k-coloring of a graph G is a function f : V (G) → S, where |S| = k. The elements of S are often called colors. A k-coloring of G is called proper if adjacent vertices are assigned different colors. Suppose that for each vertex v in G, we gave v a list L(v) of available colors. A list coloring of a graph G is a proper coloring of G where each vertex v is assigned a color from L(v). In particular, for two distinct vertices u and v, L(u) and L(v) might be different. A graph is k-choosable if every assignment L of at least k colors to each vertex guarantees an L-coloring. The choosability of a graph G is the minimum k such that G is k-choosable.
In many applications of list coloring, such as scheduling, some vertices may have preferences which are not directly captured by the lists themselves. For example, a professor may be willing to teach classes X,Y, or Z but prefers to teach X. Ideally, the scheduler can satisfy the specific requests of each professor, but it is often the case that they cannot. The goal is then to satisfy as many requests as possible. This idea motivates the following definitions.
A weighted request is a function w that assigns a nonnegative real number to each pair (v, c) where v ∈ V (G) and c ∈ L(v). For ε > 0, we say that w is ε-satisfiable if there exists an L-coloring ϕ of G such that
The unweighted variant is defined as follows. A request for a graph G with a list assignment L is a function r with domain dom(r) ⊆ V (G) such that r(v) ∈ L(v) for all v ∈ dom(r). In the special case that each vertex requests a color, i.e., dom(r) = V (G), we call such a request widespread. Analogously, for ε > 0, a request r is ε-satisfiable if there exists an L-coloring ϕ of G such that at least ε| dom(r)| vertices v in dom(r) receive color r(v). We say that a graph G with list assignment L is ε-flexible, weakly ε-flexible, or weighted ε-flexible if every request, widespread request, or weighted request, respectively, is ε-satisfiable. Note that weak flexibility does not make sense in the weighted setting since one can set some weights to 0 to turn off the requests for these vertices. If G is (weighted/weakly) ε-flexible for every list assignment with lists of length k, we say that G is (weighted/weakly) ε-flexible for lists of size k. Note that for k-colorable graphs, if the lists are exactly the same the problem becomes trivial as by permuting the colors we can achieve 1 k -flexibility [6].
The concept of ε-flexibility was introduced by Dvořák, Norin, and Postle [6]. Subsequently, it was studied for various sub-classes of planar graphs, e.g., trianglefree [5], girth six [4], or C 4 -free [10]. Graphs of bounded maximum degree were subsequently characterized in terms of flexibility [1].
A central notion in graph coloring is that of reducible configurations, which are local subgraphs that cannot appear in a smallest counterexample because their presence implies that the graph can be colored from a smaller subgraph by induction. Reducible configurations for flexibility are slightly more delicate as we explain in Section 2. Recently, Choi, Clemen, Ferrara, Horn, Ma, and Masařík [2] proposed a strengthened tool (see Lemma 1 below) for designing reducible configurations for flexibility. The authors of [2] also introduced the notion of weak flexibility defined above. They demonstrated that the weak setting allows one to create stronger reducible configurations.
We further develop this direction by strengthening the tools for handling weak flexibility; see Lemma 2 in Section 3. We exhibit our new tool by showing the following results for subclasses of planar graphs.
For an integer n ≥ 3 let B n denote the book on n vertices, i.e., the graph consisting of n -2 triangles sharing an edge. Let C n and K n denote a cycle and a clique on n vertices, respectively. Given a set of graphs F and a graph H, we say that H is F -free if there is no subgraph of H isomorphic to any of the graphs in F .
Theorem 1 There exists ε > 0 such that every planar {K 4 ,C 5 ,C 6 ,C 7 , B 5 }-free graph is weighted ε-flexible for lists of size 4.
Theorem 2 There exists ε = ε(b) > 0 such that every planar {K 4 ,C 5 ,C 6 ,C 7 , B b }-free graph is weakly ε-flexible for lists of size 4.
The results in Theorems 1 and 2 are tight as in general such graphs are not even 3-colorable. This is exemplified by the construction in Figure 1. This construction implies:
Observation 3 For every ℓ, b ≥ 5 exists a {K 4 , B b }-free planar graph G that does not contain any cycle C k of length 5 ≤ k ≤ ℓ, such that G is a not 3-colorable. Furthermore, our results follow a recent line of research trying to narrow the gap between known degeneracy upper-bounds and choosability lower-bounds, in particular on subclasses of planar graphs, as is described below. We say that a graph G is d-degenerate if each induced subgraph of G contains a vertex of degree at most d. It is easy to observe that d-degenerate graphs are (d + 1)-choosable. A similar statement holds for flexibility as well: in [6] it was proved that d-degenerate graphs with lists of size d + 2 are weighted ε-flexible. Therefore, as C 5 -free planar graphs are 3-degenerate [11], they are ε-flexible for lists of size 5. The same is true for C 6 -free planar graphs [7]. For C 3 -free graphs, Dvořák, Masařík, Musílek, and Pangrác [5] showed that they are weighted ε-flexible for lists of size 4 and that this the result is tight. Surprisingly, the discharging proof in [5] is quite involved compared to the easy observation that C 3 -free planar graphs are 3-degenerate, which implies 4choosability. An analogous result holds for {C 3 ,C 4 ,C 5 }-free graphs, where list of size 3 are sufficient for weighted ε-flexibility and the result is tight [4]. When only C 4 is forbidden, Masařík [10] proved that lists of size 5 are sufficient for weighted ε-flexibility. However, it is unknown whether the result is tight as those graphs are 4-choosable [8] (but not necessarily 3-degenerate). There were attempts to bring down the list size to 4 but so far only partial results are known in this direction: planar graphs that do not contain C 4 and C 3 at distance at most 1 [2] or {C 4 ,C 5 }-free planar graphs [12]. See [2, Table 1] for a comprehensive overview of known results for various subclasses of planar graphs. Our results aim to improve this narrow gap as they show that lists of size 4 are sufficient even for planar graphs in which some copies of C 3 and C 4 are allowed.
The purpose of this section is to informally describe some of the difficulties one faces when trying to extend a list-coloring proof to a flexibility proof. This discussion serves as the intuition behind the formal definitions in the next section.
As in previous related papers mentioned above, we use the discharging method to obtain our results. For an introduction to the discharging method see [3]. A typical discharging proof that a graph G is L-list-colorable gives a list of unavoidable reducible configurations, which are subgraphs of G that cannot appear in a minimal counterxample. The goal is to decompose
(this will be defined as a resolution later), so that any
When requests are introduced, this method becomes more difficult. To explain this, assume for simplicity that every vertex has a request. If we manage to accommodate one request from each R i and each R i has at most b vertices, then we would satisfy n/b requests, showing that G is ε-flexible for ε = 1/b, and our job would be done. However, this is not necessarily possible. Indeed, suppose v ∈ R i has some request r(v) and let ϕ be an
, there is no way to simply extend ϕ and accommodate the request of v. Thus more changes to ϕ, such as recoloring u, would have to occur to accommodate r(v). In addition to this issue, it may also be the case that r(v) cannot be satisfied because R i itself prevents it. This means that reducible configurations for flexibility need to provide slightly more freedom in the colorings they allow. The easier problem to deal with is that r(v) cannot be satisfied because R i itself prevents it. This can be patched by adding a requirement that for any one vertex x in R i , the coloring ϕ extends to R i even if x has a list of size 1 after removing the colors of already colored neighbors of
For v, this would be used in case L(v) = {r(v)} and ϕ(u) = r(v). This requirement will be called (FIX) in the formal definitions.
The problem occurring when r(v) cannot be satisfied because its neighbor u in
is more complicated to solve. The idea is the following. Instead of constructing just one L-coloring ϕ, one needs to construct Lcolorings ϕ 1 , . . . , ϕ ℓ and in some of them, u gets colored by a color different than r(v). Then ϕ 1 , . . . , ϕ ℓ can be extended to ϕ ′ 1 , . . . , ϕ ′ ℓ ′ , where r(v) is satisfied in some of them. At the end, this process gives a set of L-colorings of G and at least one of them satisfies a positive fraction of the requests. Formally, this is done by creating a probability distribution on L-colorings of G.
In order to make this idea work, there must be a sufficient variety of proper colorings for each reducible configuration. In our example, if we want to color v by r(v), we cannot use r(v) on u. We need to address this when we are coloring u and remove r(v) from its list. Further, we would need to do this for each neighbor of v in R i+1 ∪ • • • ∪ R N . This is achieved in the following way. When we are L-coloring R i , we look at all subsets I ⊆ V (R i ) of vertices that could form a neighborhood of a vertex in R 1 ∪ . . . ∪ R i-1 , i.e. in the set of not yet colored vertices. Individually for each I, we show that any proper L-coloring ϕ of R i+1 ∪ • • • ∪ R N can still be extended to R i even if we decrease the sizes of the lists of vertices in I by 1. This will be called (FORB) in the formal definitions.
To summarize, the reducible configurations for flexibility must have size bounded by a constant, any one vertex can be precolored (FIX), and for different subsets of vertices, reducing their lists sizes by 1 does not break the extendability of the coloring (FORB).
The main feature of weak flexibility is that instead of demanding in (FIX) that "any one vertex in R i can be precolored", it is enough to ask for "at least one vertex in R i can be precolored". It is then easier to satisfy this version of (FIX).
We introduce an additional trick, where we ask "at least one vertex in R i with few external neighbors can be precolored". This makes satisfying (FIX) more difficult since the reducible configurations need a vertex of small degree but it helps a lot with checking (FORB).
We use some of the notation and tools introduced in [2,[4][5][6]. In particular, our definitions are quite similar to those used in [2].
Let 1 I denote the characteristic function of I, i.e., 1
We will use f ↓ v to indicate that the list size at vertex v has been reduced to 1. In other words, f ↓ v means that v has been "precolored". A list assignment L is an
Given a set of graphs F and a graph H, a set I ⊆ V (H) is F -free if the graph H together with one additional vertex u adjacent to all of the vertices in I does not contain any subgraph isomorphic to a graph in F . Throughout the following definitions, let H be an induced subgraph of a graph G, let F be a set of graphs, and let k be a positive integer.
We say that H is an (F , k)-boundaryreducible subgraph if there exists a set R ⊆ V (H) such that R = / 0 and
Definition 2 (weak (F , k)-boundary-reducibility) We say that H is weakly (F , k)boundary-reducible if it satisfies (FORB) and there exists at least one vertex v satisfying (FIX) from Definition 1. In this case, we denote v by Fix(H).
In both of the preceding definitions, we will occasionally refer to the set V (H)\R as the boundary of the configuration and the set R as the reduced part of the configuration. Note that (FORB) in particular implies that deg A weak (F , k, b)-resolution is defined analogously, except that it uses weak (F , k)boundary-reducibility in the place of (F , k)-boundary-reducibility.
The following lemma is the main tool we use for proving weighted ε-flexibility.
Lemma 1 (Lemma 13 in [2]) For integers k ≥ 3 and b ≥ 1 and for a set F of forbidden subgraphs, let G be an F -free graph with an (F , k, b)-resolution. Then there exists an ε > 0 such that G is weighted ε-flexible for lists of size k. Furthermore, if the request is widespread and G has a weak (F , k, b)-resolution, then G is weakly ε • 1 b -flexible for lists of size k.
For the proof of Theorem 2 we prove a stronger version of Lemma 1 tailored to the setting of weak flexibility. For this, we define new "enhanced" versions of weak (F , k)-boundary-reducibility and of a weak (F , k, b)-resolution. We will now require Fix(H) to contain only vertices v satisfying deg G (v) -deg R (v) ≤ k -3. This change will allows us to consider smaller sets for the (FORB) condition.
Before proceeding further, observe that (FORB) in the enhanced version is easier to check because I is of size at most k -3, instead of k -2 in the non-enhanced version. However, (FIX) in the enhanced version has an additional restriction on the degree of vertices in Fix(H), which makes it more difficult to satisfy. Note that in general, the (FORB) condition on a single vertex
In particular, a vertex of degree k -2 is no longer reducible under the enhanced definition. We overcome this obstacle by allowing (k -2)-vertices in a resolution under special conditions. Forbidding books B ℓ helps with satisfying these special conditions. By doing this we can have both: a vertex of degree k -2 is reducible in our setting, and in addition we obtain subgraphs H that are reducible under the enhanced weak (F , k)-boundary-reducibility definition, given that certain special circumstances occur. This rather technical improvement helps substantially in reducing the complexity of the analysis of the discharging process for the graph classes studied in this paper. Note that further generalization of this idea may be possible, but for lack of use in this paper we will not aim to formulate this in the full generality.
If G is a graph satisfying the conditions of Definition 4 and
Let G be a graph, H its subgraph and
such that all the following three conditions hold:
G M is a weak (F , k)-boundary-reducible graph with empty boundary and order at most b, G M+1 : = / 0, and
The following is satisfied: (TIGHT) For every 1 ≤ j ≤ M, there are at most β different H j -tight vertices v i , where
Note that in Definition 5
A natural way to satisfy (TIGHT) condition is to show that whenever there is an H j such that more than
If two adjacent vertices have many common neighbors, we get a book, which will be in F .
We are now ready to state and proof our main lemma.
Lemma 2 (Reducible configurations for weak flexibility) For integers k ≥ 4, b ≥ 1, β ≥ 0, and for a set F of forbidden subgraphs, let G be a F -free graph with an enhanced weak (F , k, b, β )-resolution. Then, there exists an ε > 0 such that G is weakly ε-flexible for lists of size k.
The proof of the lemma is similar to the proof of Lemma 1 as it appeared in [2, Lemma 13]. In particular, we explicitly formulate a few arguments in their proof as a separate claim (Claim 4 below) that we use in our proof. We will also need the following Lemma 3, which is Lemma 12 in [2].
Let G be a graph with a weak (F , k, b)-resolution R. Let AllFix(G) denote the union of all Fix(H) over all reducible subgraphs H in the resolution R.
Proof (Proof of Lemma 2) For 1 ≤ j ≤ M + 1, let H j be the set of all H j -tight subgraphs where the (TIGHT) property applies. Let H i ∈ H j for some i and j. This means that H i is a single vertex with k -2 ≥ 2 neighbors in H j . Hence H i = / 0. Now, we refactor the enhanced weak (F , k, b, β )-resolution R into an enhanced weak (F , k, b + β , 0)-resolution R ′ . To do so, we attach all H j -tight subgraphs to H j and thus we create a larger configuration H ′ j . The vertices in tight subgraphs are not part of any Fix set. Formally
Observe that by the (TIGHT) property, the size of the resulting H ′ j will be upper-bounded by b + β and that H ′ j is enhanced weakly (F , k)-boundary-reducible or only weakly (F , k)-boundaryreducible (provided its neighbourhood is always a loose or small set) if it is not empty. We simultaneously remember both R and R ′ , since each time we are using H ′ j (or G ′ j ) we are referring to R ′ and each time we are using H j (or G j ) we are referring to R.
The next step is to create a probability distribution on L-colorings ϕ of G i for all i starting with G ′ M . Let p = k -(b+β ) and ε ′ = p k-1 . We are going to show that each i satisfies the following properties:
(i) for every v ∈ AllFix(G ′ i ) and a color c ∈ L(v), the probability that ϕ(v) = c is at least ε ′ , and (ii) for every color c and every F -free set I in G ′ i of size at most k -3, the probability that ϕ(v) = c for all v ∈ I is at least p |I| , and (iii) for every color c and every loose
Note that for G ′ M+1 all of the properties trivially hold. Note that Property (i) on G ′ 0 = G 0 = G immediately implies that G with L is weakly ε ′ • 1 b -flexible by Lemma 3 and therefore weakly ε-flexible for ε = ε ′ b . We will make use of the following claim proven implicitly in [2].
Claim 4 (Implicit in the proof Lemma 13 in [2])) Suppose that we have an enhanced weak (F , k, b + β , 0)-resolution and a probability distribution on L-colorings of G ′ i+1 satisfying Properties (i), (ii), and (iii) on G ′ i+1 . If for each vertex v ∈ Fix(H ′ i ) and for each I = N(v) ∩ H ′ j where j > i one of the following holds:
then there exists a probability distribution on L-colorings of G ′ i such that Properties (i), (ii), and (iii) are satisfied on G ′ i . In order to use Claim 4, we need verify (a) and (b). If
We do it by showing v is not H ′ j tight for any j ≥ i in the following claim. It implies that for H ′ i , either (a) or (b) is satisfied. In particular, we will show that we got rid of all tight subgraphs when we refactored R into R ′ . Claim 5 There are no i < j such that H ′ i is H ′ j -tight. Proof Suppose for contradiction that H ′ i is H ′ j -tight for some i < j. By the definition,
j is a union of H j and vertices W , where every w ∈ W has k -2 neighbors in H j . Since v is not H j -tight, it has at most k -3 neighbors in H j and at least one in W . Notice that every vertex w in W has k -2 neighbors in H j hence a list of k -1 colors suffices for extending any coloring of H j to w greedily. This and the (FORB) property for H j imply that v is not 3 ⌋. Proof If not, then v is adjacent to three faces f , g, h, each of them of size at most 4, such that f , g share an edge and g, h share an edge. But this induces a cycle C i with 5 ≤ i ≤ 7, a contradiction.
In all the figures in the paper, black vertices have all their incident edges drawn, whereas a white vertex may have more edges incident than drawn (since white vertices are in the boundary). We wish to point out that the reducible configurations are meant to be induced subgraphs by definition, and we will use them as such in the discharging part of the proof. The only configuration, where two external edges can be identified is (C2) and it gives (C3), which we explicitly list. It can be straightforwardly checked that no identification of vertices in (C1)-(C15) is possible since otherwise, it creates a forbidden subgraph. Lemma 5) It is straightforward to check that each configuration (C1)-(C15) satisfies the (FIX) and (FORB) conditions in Definition 1. However, checking all the cases is rather tedious. Hence we developed a simple computer program that does it, see http://lidicky.name/pub/flexibility foot_0 . In particular, a greedy coloring works in all cases. For an interested reader who wishes to check some cases by hand, we added list sizes to Figures 2 and3. We also provide here proofs showing that (C2) and (C5) are (F , 4)-boundary-reducible. Together, these two configurations demonstrate how to prove that the remaining configurations are reducible.
The two reducible configurations H 1 and H 2 corresponding to (C2) and (C5), respectively are depicted in Figure 4. The reduced parts R 1 = H 1 and R 2 ⊂ H 2 are provided as well. Finally, we have labeled each vertex in the figure with the value of the function 4 -deg By definition, checking the (FIX) condition for any subgraph H with reducible part R is equivalent to showing that for each v ∈ V (R), R can be properly colored after assigning each vertex a list of size ((4
It is clear by inspection that this is the case for (C2) = H 1 = R 1 , and hence we only need to check the (FORB) condition for (C2). Since (FIX) is already verified, it implies (FORB) for subsets of size one in R. It remains to verify (FORB) for subsets of size two in R.
If we apply (FORB) to a and c, then both a and c will be left with one available color in their lists. Vertex b still has three colors in its list. Therefore, we can greedily color a, c, and b in this order to obtain a proper coloring for (C2). If we apply (FORB) to a and b, then the color for a will be fixed, and each of b and c will be left with two possible colors. Therefore, we can greedily color a, b, and c in this order to obtain a proper coloring for (C2). By symmetry, the case of applying (FORB) to b and c is also verified, implying that (C2) is reducible.
Let H 2 be a subgraph of G isomorphic to (C5). Let R 2 ⊂ H 2 denote the reducible part of (C5), i.e. the subgraph of H 2 induced by vertices u 1 , . . . , u 4 . For each i = 1, . . . , 4, we will check the (FIX) condition for u i . Let L i be an arbitrary list assignment where each vertex in R is assigned a list of size ((4 -deg H + deg R ) ↓ u i ). We will now show that R can be properly colored. In each case we list the order of vertices in greedy coloring.
-
Next we need to verify that H satisfies the (FORB) condition. However, only one subset of R of size two is F -free: {u 1 , u 2 }. In that case R can be colored greedily in the following order u 1 , u 2 , u 4 , u 3 . Thus, (C5) is a reducible configuration. ⊓ ⊔
In this section we prove the following lemma, which by Lemma 1 implies Theorem 1.
Lemma 6 Let G be a connected {K 4 ,C 5 ,C 6 ,C 7 , B 5 }-free plane graph. Then G contains at least one of the reducible configurations (C1)-(C13).
Proof Suppose for contradiction that G is a connected {K 4 ,C 5 ,C 6 ,C 7 , B 5 }-free plane graph that contains none of the configurations (C1)-(C13). We use discharging to obtain a contradiction with Euler's formula. We denote the initial charge by ch. For every vertex v, we let ch(v) = deg(v) -4, and for every face f we let ch( f ) = ℓ( f ) -4, where ℓ(F) is the length of the facial walk. For convenience we will also assign charge to the edges of G. The initial charge is 0 for each edge. By Euler's formula, the total sum of initial charges is -8.
We sequentially apply the following rules (see also Figures 5 and6) that move the charge around, while keeping the sum of charges unchanged. The charge at the end is called the final charge. The final charges will be all nonnegative, contradicting that their sum is -8. Proof Given that G does not contain any faces of length 5, 6 or 7, we consider 8 + -faces, 4-faces, and 3-faces as three separate cases covering everything.
Suppose that f is an 8 + -face. Then the initial charge of f is equal to ℓ( f ) -4. By (R1) and (R2), f sends at most 1 2 for each of these edge that is not a bridge and charge 1 to each bridge by (R2). This means that f sends at most ℓ( f ) 2 ≤ ℓ( f ) -4 total charge. Since (R1) and (R2) are the only rules requiring an 8 + -face to send out charge, every 8 + -face has nonnegative final charge.
Suppose that f is a 4-face. Then f has its initial charge 0. Since C 5 , C 6 , and C 7 are forbidden subgraphs, f must be incident with four 8 + -faces. By (R1), each face sharing an edge with f sends charge 1 2 to f for every edge they have in common, leaving f with a total charge of 2 before applying (R2)-(R9). Given that (C2) is a reducible configuration, f cannot contain more than two 3-vertices. Thus, (R4) applies to f at most twice, which decreases the charge at f by at most 2. Since no other rules apply to 4-faces, f has nonnegative final charge.
Next suppose that f is a 3-face that is not contained in a diamond. Every face incident to f must be an 8 + -face since C 5 , C 6 , and C 7 are forbidden subgraphs. This means that after applying (R1), f has charge 1 2 . Among rules (R2)-(R9), only (R5) requires a 3-face to send out charge. If applies to f , then it only requires f to send a charge of 1 2 . This means that f has nonnegative final charge. Lastly, assume that f is a 3-face contained in a diamond D. Then f shares one edge with another 3-face. Since C 5 , C 6 , and C 7 are forbidden subgraphs, f shares its other two edges with 8 + -faces. By (R1), f receives charge at least 1 2 for each edge it shares with an 8 + -face, leaving f with charge at least 0 before applying (R2)-(R9). None of these rules, however, demand charge from a 3-face that is contained in a diamond, implying that f will end with nonnegative charge. As we have considered all possible faces in G, this completes the proof of Claim 6. ♦
The final charge of every edge of G is nonnegative.
Proof Let e = uz be an edge of G. If e is incident with a 3-face or a 4-face, then none of the rules apply to e and there is nothing to prove. Otherwise, e has charge 1 after applying (R2). As (R3) is the only rule that requires any edge to send out charge, it suffices to verify that e will never be asked to give more than 1 charge under (R3). If u and z are both 3-vertices, then only (R3a) applies to e and the edge sends exactly 1 2 to each of u and z. If u is a 3-vertex and z is a 4 + -vertex, then only (R3b) applies, and e send exactly 1 to u.
If u is a 4 + -vertex and z is a 5 + -vertex, then (R3) does not apply with z and e sends charge at most 1 using either (R3c) or (R3d).
The remaining case is that both u and z are 4-vertices. The rules demand e to send charge more than 1 if by symmetry (R3c) applies with u and one of (R3c) and (R3d) applies with z. However, this would give reducible configurations (C9) and (C12), respectively. Therefore, no edge in G that begins with charge 1 will ever be asked to send out more than 1 total charge, completing the proof of Claim 7.
♦ Claim 8 The final charge of every 4 + -vertex is nonnegative.
Proof Suppose that v is a 4-vertex. The initial charge of v is 0, and there are no rules requiring v to send out charge, so v will end with nonnegative charge. Next suppose that v is a 5-vertex. Then the initial charge of v is 1. Only (R6) and (R7) require a 5-vertex to distribute charge. Therefore, we may assume that v is incident with at least one diamond. Given that G does not contain any C 5 , C 6 , C 7 , or B 5 subgraphs, v is incident with at most two diamonds.
First suppose that v is incident with exactly one diamond D. If v is a middle vertex of D then only (R6) applies to v, and if v is a side vertex of D then only (R7) applies to v. As neither of these two rules will require v to send out charge more than 1, v will end with nonnegative charge.
Next suppose that v is incident with two diamonds D 1 and D 2 . Since G does not contain any C 5 , C 6 , C 7 , or B 5 subgraphs, D 1 and D 2 must be edge disjoint. Since deg(v) = 5, v cannot be a middle vertex of both diamonds. If v is a side vertex of both diamonds, then only (R7) applies to v. As (R7) will not require v to send charge more than 1 2 to either diamond, v will end with nonnegative charge. Therefore, we may assume that v is a middle vertex of D 1 and a side vertex of D 2 . In this case, it is possible that both (R6) and (R7) apply to v. Among the subcases of (R6), only (R6a) requires v to send out charge for more than 1 2 , and (R7) will never ask v send out charge more than 1 2 . Given that configuration (C8) is reducible, (R6a) cannot apply with (R7a). Next, given that configuration (C10) is reducible, (R6a) cannot apply with (R7b). By assumption of (R7c), (R6a) cannot apply with (R7c). Therefore v is never asked to send more than 1, implying that v will end with nonnegative charge. Now suppose that v is a 6 + -vertex. The only rules that apply to v are (R8) and (R9). Under these rules, v sends at most 1 to all diamonds that contain v as a middle vertex, and v sends at most 1/2 to all diamonds that contain v as a side vertex. Assume that v is the middle vertex of k distinct diamonds, and incident to m other faces of size 3. By Lemma 4, the final charge of v is at least
-4 is nonnegative whenever deg(v) ≥ 6. This completes the proof of Claim 8. ♦
The final charge of every 3-vertex that is not contained in a diamond is nonnegative.
Proof Let v be a 3-vertex that is not contained in a diamond. Then the initial charge of v is -1. As there are no rules requiring v to send out charge, we only need to verify that v will receive charge at least 1. First suppose that v is not incident to any 3-faces or 4-faces. Then each of the three edges incident to v receive charge 1 under (R2).
Next, each of these edges sends 1 2 to v by (R3), leaving v with a charge of 1 2 .
Now suppose that v is incident to at least one 4-face f . By (R4), v receives 1 from f and we are done. Therefore, we may assume that v is not incident to any 4-face, and that v is incident to at least one 3-face T . By assumption, T is not contained in a diamond.
-Case 1: T contains another 3-vertex. In this case, v must be adjacent to a 4 + -vertex u that is not contained T , since (C2) is reducible. Then by (R3b), v receives a charge of 1 from the edge uv. -Case 2: T contains two 4 + -vertices. Again, let u be the neighbor of v that in not contained in T . Here, v will receive at least 1 2 from (R3). With that being said, T will send the remaining 1 2 to v under (R5). This completes the proof of Claim 9. ♦
The final charge of every 3-vertex that is incident to a diamond is nonnegative.
Proof Assume that v is a 3-vertex incident to a diamond D. Since (C2) and are there is at most one other 3-vertex incident to D. Since the initial charge of v is -1, and there is no rule requiring a 3-vertex to send charge, it suffices to show that v will always receive charge at least 1 after applying rules (R1)-(R9). We consider the following cases.
Case 1: v is the only 3-vertex incident to D and v is a side vertex of D. Given the list of forbidden subgraphs in G, the other two faces incident to v must be 8 + -faces. Hence by (R3), v receives charge at least 1 2 from the only edge incident to v that is not a part of D. There are three subcases to Case 1 showing how v gets another 1 2 of charge. In the next section we will prove the following theorem, showing that (D1)-(D12) are unavoidable. We remark that no identification of vertices in (D1)-(D12) is possible since otherwise, it creates a forbidden subgraph. It is possible that some external edges can be identified in (D8), (D9), and (D11). We explicitly list those cases in Figure 8 as (D8'), (D9'), (D11'), and (D11").
Theorem 11 Every {K 4 ,C 5 ,C 6 ,C 7 }-free planar graph contains one of (D1)-(D12).
Let F = {K 4 ,C 5 ,C 6 ,C 7 , B ℓ } for any fixed ℓ. We will show that (D2), (D3), and (D5)-(D12) are enhanced weakly (F , 4)-boundary-reducible configurations. We will also show that (D4) is only a weakly (F , 4)-boundary-reducible configuration. However, the only neighbors of the vertices in the reducible part of (D4) are the nonadjacent vertices in the boundary, and all non-adjacent pairs that do not forbid F in each of (D1)-(D12) form loose sets, implying that the condition required by the enhanced weak resolution is satisfied.
In order to use Lemma 2, we want to have an enhanced weak (F , 4, b, β )resolution for some β and b. First, we check the condition (TIGHT) in the following lemma.
The number of H-tight vertices is at most β ≤ 10ℓ.
Proof Let H be one of (D2)-(D12) and v be an H-tight vertex adjacent to u and w in H. First, suppose that u and w are not adjacent. There are no non-edges in (D2) and (D4). The non-edge in (D9) forms a loose set. By inspection of each pair of non-adjacent vertices in (D5)-(D8) and (D10)-(D12), we observed that if v was adjacent to any of these pairs, we would obtain a C 5 or a C 6 , contradicting that G is F -free.
Second, suppose that uw is an edge. As B ℓ is in F , the number of H-tight vertices for uv is at most ℓ -3. Since H is one of (D2)-(D12), it has at most 10 edges. This bounds that the total number of H-tight vertices as β ≤ 10(ℓ -3) ≤ 10ℓ.
⊓ ⊔
The configurations (D2), (D3), (D5)-(D12) are enhanced weakly (F , 4)boundary-reducible. See Figure 8 for illustration.
Proof Given the rules for enhanced weak (F , k)-boundary reducibility, it is straightforward to verify that configurations (D2)-(D12) are reducible. We also provide a computer program at http://lidicky.name/pub/flexibility foot_1 to do so. One notable difference is that the greedy algorithm is not always sufficient. We also added test for Gallai tree, which helped. Just greedy algorithm could end with a diamond, where middle vertices have lists L of size 3 and side vertices would have lists of size 2, which is not a Gallai tree and hence it is L-colorable, but not in a greedy way.
In order to highlight the difference between regular and weak reducibility, we will give a short proof that (D10) is weakly (F , k)-boundary reducible, but not (F , k)boundary reducible. Let R be a subgraph of a graph G defined by configuration (D10). Let a, b, c and d be vertices of R. The initial list sizes of a list assignment L as defined by the function (4 -(deg G + deg R )) are given in Figure 7. First we will show that we cannot fix the color of a and still properly color R. Indeed, if the lists of b and c are identical and both contained the color assigned to a, there would be no proper L-coloring of R.
That being said, if we fix the color of any other vertex in R, then we will still be able to properly L-color R. Therefore, we can only apply (FIX) to a subset of the vertices of R. Given the graphs in F , it immediately follows that the graph H = R is weakly (F , k)-boundary reducible, but as we have show, it is not (F , k)-boundary reducible.
In the enhanced version, the main trick is that we never need to check (FORB) on two adjacent vertices. We do that by allowing (FIX) only on vertices, where their external neighbors are non-adjacent. The easiest way to do so is to use (FIX) only on vertices that have at most 1 external neighbor. In case of (D10), the only option for (FIX) is the vertex d.
⊓ ⊔ (R7) For every 3-face f = {v, u, w} and 5-vertex v such that f is not part of a diamond having v as a middle vertex, the following applies. (R7a) If both deg(u) ≥ 4 and deg(w) ≥ 4, then v sends charge 1 to f . (R7b) Otherwise v sends charge 2 to f . (R8) Every 6 + -vertex v sends charge 1 to every 4-face adjacent to it, and 2 to every 3-face f adjacent to it, unless f is part of a diamond having v as a middle vertex. Every 6-vertex v sends charge 7 4 to every 3-face of every Dia(6 -3, 3, 4) that contains v. (R10) Every 6-vertex v sends charge 3 2 to every 3-face of Dia(6 -3, 4, 4) that contains v. (R11) Every 6-vertex v sends charge 5 4 to every 3-face of any diamond d having v as a middle vertex, where (R9) and (R10) did not apply. (R12) Every 7 + -vertex v sends charge 7 4 to every 3-face of any diamond having v as a middle vertex. (R13) For every two 3-faces f , g that form a diamond, if g has positive charge while f has negative charge, then g gives f all its positive charge. Proof There are no vertices of degree less than 3, by (D1). The initial charge of a 3-vertex is 0, and this does not change in the discharging process. A v has initial charge 2. It can be adjacent to at most two 4 --faces, or otherwise a cycle C k with 5 ≤ k ≤ 7 is created. Therefore (R3) applies on v at most twice and no other rules apply. Hence v has a nonnegative final charge. Let v be a 5-vertex that is not a middle vertex of a diamond. Note that v can be adjacent to at most two faces of size at most 4, or otherwise a cycle C k with 5 ≤ k ≤ 7 is created. Thus, the initial charge of v is 4, and (R4) and (R7) are applied together at most twice, implying v has nonnegative final charge.
Let v be a 5-vertex that is a middle vertex of a diamond d. Then v is adjacent to at most one more face f of size at most 4, and f does not share any edge with d, or otherwise a cycle C k with 5 ≤ k ≤ 7 is created. If (R5) does not apply to v, then by (R4), (R6) and (R7), v sends 1 to each of the two 3-faces in d and at most 2 to f , leaving v with final nonnegative charge. Suppose (R5), where v sends charge 3 to the faces in d, applies to v. If v sends charge of at most 1 to f , then it has final nonnegative charge. So by (R4) and (R7a) we may assume that f is a triangle {v, u, w} with d(u) = 3 (and d(w) ≤ 4). See Figure 11 for an illustration. But then G contains (D7), (D11), or (D8) as d is Dia(5 -3, 4, 4), Dia(5 -3, 3, 5 + ), or Dia(5 -5, 3, 3), respectively. Hence (R7b) does not apply to v and the final charge is nonnegative.
Let v be a 6-vertex that is the middle vertex of k diamonds and it is adjacent to m faces of size 3 or 4 that are not part of a diamond in which v is a middle vertex. By Lemma 4, 6 ≥ 3k + 2m. Recall that ch(v) = 6. Suppose k = 2, then m = 0. By (D12) and (D3), (R9) cannot apply twice and (R9) cannot apply at the same time as (R10). Then by (R9)-(R11), the final charge of v is at least 6 -3.5 -2.5 = 0 or 6 -3 -3 = 0. If k = 1 and m ≤ 1, then by (R8)-(R11), the final charge of v is at least 6 -3.5 -2 > 0. Finally, if k = 0 and m ≤ 3 then by (R8), the final charge of v is at least 6 -3 • 2 = 0.
Let v be a 7 + -vertex that is the middle vertex of k distinct diamonds, and v is adjacent to m faces of sizes 3 and 4 that are not part of a diamond in which v is a middle vertex. Then by Lemma 4, deg(v) ≥ 3k + 2m. By (R12) v sends total weight of 3.5k to the k diamonds in which v is a middle vertex, and by (R8) it sends at most 2m to the other faces of size at most 4 it is adjacent to. The final charge of every face that is not contained in a diamond is nonnegative.
Proof By (R1) and (R2), an 8 + -face f sends out a total charge of at most ℓ( f ) 4 . Thus the final charge of f is at least ℓ( f ) -6 -ℓ( f ) 4 = 3ℓ( f ) 4 -6 which is nonnegative if ℓ( f ) ≥ 8.
Let f be a 3-face that is not part of any diamond. Then the faces sharing an edge with f must be of size at least 8, since otherwise one of them is of size at most 4, which forces a diamond or a cycle C i with 5 ≤ i ≤ 7 together with f . Hence (R1) applies three times with f and f has charge -3 + 3 4 = -2.25 after (R1). By (D1) and (D2), one of the following holds (see Figure 12):
(1) f is T (3, 3, 5 + ), or (2) f is T (3, 4 + , 4 + ), or (3) f if T (4 + , 4 + , 4 + ).
-Dia (5 -3, 3, 3), Dia (5 -3, 3, 4) Reducible by (D9) and (D10). -Dia(5 -3, 3, 5 + )
In this case, (R5) applies to u and (R7b) or (R8) applies to y. This gives charge 2 • 1.5 + 2 = 5. Hence the final charges of f and g are nonnegative.
-Dia (5 -3, 4, 4) In this case, (R5) applies to u. In addition (R3) applies to both x and y. This gives charge 2 • 1.5 + 1 + 1 = 5. Hence the final charges of f and g are nonnegative.
-Dia(5 -3, 4 + , 5 + )
In this case, (R6) applies to u. In addition (R3), (R7b), or (R8) applies to x and (R7b), or (R8) to y. This gives charge at least 2 • 1 + 1 + 2 = 5. Hence the final charges of f and g are nonnegative.
-Dia (6 -3, 3, 3) Reducible by (D9). -Dia (6 -3, 3, 4) By (R9), u contributes charge 3.5 and by (R4), y contributes charge 1. Let z be a neighbor of x that is not u or v. By (D9), deg(z) ≥ 4 Hence the application of (R2b) around x contributes charge 1/2. This gives charge 3.5 + 1 + 0.5 = 5 in total.
Hence the final charges of f and g are nonnegative.
-Dia(6 -3, 3, 5 + ) By (R11), u contributes charge 2.5 and by (R7b) or (R8), y contributes charge 2.
Let z be a neighbor of x that is not u or v. By (D9), deg(z) ≥ 4 Hence the application of (R2) around x contributes charge 1/2. This gives charge 2.5 + 2 + 0.5 = 5 in total. Hence the final charges of f and g are nonnegative.
-Dia (6 -3, 4, 4) By (R10), u contributes charge 3 and by (R3), x and y each contribute charge 1. This gives charge 3 + 1 + 1 = 5 in total. Hence the final charges of f and g are nonnegative.
-Dia(6 -3, 4 + , 5 + ) By (R11), u contributes charge 2.5, by (R3), (R7b) or (R8), x contributes charge at least 1, and by (R7b) or (R8), y contributes charge 2. This gives charge at least 2.5 + 1 + 2 = 5 in total. Hence the final charges of f and g are nonnegative.
-Dia(7 + -3, 3, 3)
Reducible by (D9). -Dia(7 + -3, 3, 4 + ) By (R12), u contributes charge 3.5, by (R3), (R7b) or (R8), y contributes charge at least 1. Let z be the neighbor of x that is not u or v. By (D9), deg(z) ≥ 4 Hence the application of (R2b) around x contributes charge 1/2. This gives charge at least 3.5 + 1 + 0.5 = 5 in total. Hence the final charges of f and g are nonnegative.
-Dia(7 + -3, 4 + , 4 + ) By (R12), u contributes charge 3.5, by (R3), (R7b) or (R8), x and y each contribute charge at least 1. This gives charge at least 3.
This program is also available as a part of the sources in our arXiv submission[9] (file reducible_configurations.sage).
This program is also available as a part of the sources in our arXiv submission[9] (file reducible_configurations.sage).