ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 21 (2021) #P2.08 / 283–299 https://doi.org/10.26493/1855-3974.2398.7d5 (Also available at http://amc-journal.eu) The polynomial method for list-colouring extendability of outerplanar graphs Przemysław Gordinowicz * , Paweł Twardowski Institute of Mathematics, Lodz University of Technology, Al. Politechniki 10, Łódź, Poland Received 3 August 2020, accepted 28 June 2021, published online 25 October 2021 Abstract We restate theorems of Hutchinson [4] on list-colouring extendability for outerplanar graphs in terms of non-vanishing monomials in a graph polynomial, which yields an Alon- Tarsi equivalent for her work. This allows to simplify her proofs as well as obtain more general results. Keywords: Outerplanar graph, list colouring, paintability, Alon-Tarsi number. Math. Subj. Class. (2020): 05C10, 05C15, 05C31 1 Introduction In his famous paper [8] Thomassen proved that every planar graph is 5-choosable. Actually, to proceed with an inductive argument, he proved the following stronger result. Theorem 1.1 ([8]). Let G be any plane near-triangulation (every face except the outer one is a triangle) with outer cycle C. Let x, y be two consecutive vertices on C. Then G can be coloured from any list of colours such that the length of lists assigned to x, y, any other vertex on C and any inner vertex is 1, 2, 3, and 5, respectively. In other words vertices x and y can be precoloured in different colours. Basically, this theorem implies that any outerplanar graph is 3-choosable. Moreover, lists of any two neighbouring vertices can have a deficiency. To formalise this fact we say that a triple (G, x, y), where G is outerplanar graph, x, y ∈ V (G) are neighbouring vertices is (1, 2)- extendable in the sense that G is colourable from any lists whose length is 1, 2 and 3 for vertex x, y and any other vertex, respectively. *Corresponding author. E-mail addresses: pgordin@p.lodz.pl (Przemysław Gordinowicz), pawel.twardowski@dokt.p.lodz.pl (Paweł Twardowski) cb This work is licensed under https://creativecommons.org/licenses/by/4.0/ 284 Ars Math. Contemp. 21 (2021) #P2.08 / 283–299 Hutchinson [4] analysed extendability of outerplanar graphs, in the case when the se- lected vertices are not adjacent, showing that for any two vertices x, y of outerplanar graph G a triple (G, x, y) is (2, 2)-extendable. Of course, it is enough to prove this for outerplane 2-connected near-triangulation only, as each outerplane graph can be extended to such a graph just by adding some edges. The main theorem was the following. Theorem 1.2 ([4]). Let G be outerplane 2-connected near-triangulation and x, y ∈ V (G), x ̸= y. Let C : V (G) → {1, 2, 3} be any proper 3-colouring of G. Then (i) (G, x, y) is not (1, 1)-extendable; (ii) (G, x, y) is (1, 2)-extendable if and only if C(x) ̸= C(y); (iii) (G, x, y) is (2, 2)-extendable. Indeed, it is enough to prove the above theorem for near-triangulations with exactly 2 vertices of degree 2 and to let x and y be these degree 2 vertices. Hutchinson called such configurations fundamental subgraphs. Such a configuration can be obtained by succes- sively shrinking the outerplane near-triangulation along some chord (inner edge) that sepa- rates the component of the graph not containing vertices x and y (in case when xy ∈ E(G) this reduces to an edge xy). The general result follows now by succesive colouring of shrank parts using Theorem 1.1 — the chord is an outer edge of the shrank component and its endpoins (already coloured) are these 2 precoloured vertices. The details are in [4]. Also in [4], Hutchinson provided further results about extendability of general outerplanar graphs, for which the conditions are more relaxed than those of Theorem 1.2, allowing for (1, 1)-extendability. One important thing is that the proper 3-colouring C mentioned in the theorem above is not in any way connected to possible list colouring of G, but is rather an inherent property of the graph. This is due to the fact that every 2-connected outerplane near triangulation has an unique (up to permutation) 3-colouring, i.e the vertices graph can be uniquely partitioned into 3 groups so that in every proper 3-colouring of the graph the vertices in the same group will always have the same colour (the groups in this partition are called colour classes, as the partition defines an equivalence relation). The reason for this is that the graph consists entirely of triangles, and every vertex of a given triangle needs to be of different colour. The situation of particular importance is when two vertices are in the same colour class. This can be forced in two ways. One, mentioned in [4], is the so called chain of diamonds, where the diamond is understood as K4 minus an edge. It is obviously a 2-connected outerplane near triangulation, and the two non-neighbouring vertices are always of the same colour. Therefore is we link diamonds together glueing them by the vertices of degree 2, each of the linking vertices will have the same colour. The second way is to attach a diamond to diamond along the common edge (cf. [6]). Both of those ways can be seen on Figure 1. Recently, Zhu [10] strengthened the theorem of Thomassen in the language of graph polynomials showing that Alon-Tarsi number of any planar graph G satisfies AT (G) ≤ 5. His approach utilizes a certain polynomial arising directly from the structure of the graph. This graph polynomial is defined as: P (G) = ∏ uv∈E(G),u 2 (with an exception when G is a triangle), as ỹ and z̃ have a common neighbour. Now, we may consider P (G) using the inductive assumption. There are three possible cases: 1. η̃1 = 0. As η̃1 = 0 and {η̃2, η̃3} = {−1, 1}, we know that: P (G) = Q(G) + η̃2xv 2 1 . . . v 2 nỹ 1z̃1 + η̃3xv 2 1 . . . v 2 nỹ 2z̃0 = Q(G) + η̃2xv 2 1 . . . v 2 nỹ 1z̃1 − η̃2xv21 . . . v2nỹ2z̃0 = Q(G) + η̃2xv 2 1 . . . v 2 n(ỹ 1z̃1 − ỹ2z̃0). P. Gordinowicz and P. Twardowski: The polynomial method for list-colouring extendability . . . 287 Now, P (G′) = P (G)(ỹ − y)(z̃− y) = P (G)(ỹz̃− ỹy − z̃y + y2), thus: P (G′) = (Q(G) + η̃2xv 2 1 . . . v 2 n(ỹ 1z̃1 − ỹ2z̃0))(ỹz̃− ỹy − z̃y + y2) = Q(G)(ỹz̃− ỹy − z̃y + y2) + η̃2xv21 . . . v2n(ỹ2z̃2y0 − ỹ2z̃1y1− − ỹ1z̃2y1 + ỹ1z̃1y2 − ỹ3z̃1 + ỹ3y1 + ỹ2z̃1y1 − ỹ2z̃0y2) = Q′(G′) + η̃2xv 2 1 . . . v 2 n(ỹ 2z̃2y0 − ỹ1z̃2y1 − ỹ2z̃0y2) Now either z = ỹ and vn+1 = z̃, respectively, or the inverse may occur. In the first case, we have: P (G′) = Q′(G′) + η̃2xv 2 1 . . . v 2 n(v 2 n+1y 0z2 − v2n+1y1z1 − v0n+1y2z2), thus {η1, η2} = {−1, 1} and η3 = 0, with the last monomial going into Q′(G′). With analogous calculations, in the second case we have {η1, η3} = {−1, 1} and η2 = 0. As Q′(G′) obviously contains only monomials of the form ηxαxvα11 . . . v αn+1 n+1 y αyzαz , η ̸= 0, (αx, α1, . . . , αn+1) ̸= (1, 2, . . . , 2), it can assume the role of Q(G), and the case is finished. 2. η̃2 = 0. As η̃2 = 0 and {η̃1, η̃3} = {−1, 1}, we know that: P (G) = Q(G) + η̃1xv 2 1 . . . v 2 nỹ 0z̃2 + η̃3xv 2 1 . . . v 2 nỹ 2z̃0 = Q(G) + η̃1xv 2 1 . . . v 2 nỹ 0z̃2 − η̃1xv21 . . . v2nỹ2z̃0 = Q(G) + η̃1xv 2 1 . . . v 2 n(ỹ 0z̃2 − ỹ2z̃0). And then: P (G′) = (Q(G) + η̃1xv 2 1 . . . v 2 n(ỹ 0z̃2 − ỹ2z̃0))(ỹz̃− ỹy − z̃y + y2) = Q(G)(ỹz̃− ỹy − z̃y + y2) + η̃1xv21 . . . v2n(ỹ1z̃3y0 − ỹ1z̃2y1 − ỹ0z̃3y1+ + ỹ0z̃2y2 − ỹ3z̃1y0 + ỹ3z̃0y1 + ỹ2z̃1y1 − ỹ2z̃0y2) = Q′(G′) + η̃1xv 2 1 . . . v 2 n(ỹ 0z̃2y2 − ỹ1z̃2y1 − ỹ2z̃0y2 + ỹ2z̃1y1) Continuing as in case 1, when z = ỹ and vn+1 = z̃, respectively, we have {η2, η3} = {−1, 1} and η1 = 0. In the inverse case, when vn+1 = ỹ and z = z̃, there is {η2, η3} = {1,−1} and η1 = 0. Q′(G′) can again assume the role of Q(G), and this case is also done. 3. η̃3 = 0. This case is handled analogously as η̃1 = 0, interchanging the roles of ỹ and z̃. Here we have: P (G) = Q(G) + η̃1xv 2 1 . . . v 2 nỹ 0z̃2 + η̃2xv 2 1 . . . v 2 nỹ 1z̃1 = Q(G) + η̃2xv 2 1 . . . v 2 nỹ 1z̃1 − η̃2xv21 . . . v2nỹ0z̃2 = Q(G) + η̃2xv 2 1 . . . v 2 n(ỹ 1z̃1 − ỹ0z̃2). And then: P (G′) = (Q(G) + η̃2xv 2 1 . . . v 2 n(ỹ 1z̃1 − ỹ0z̃2))(ỹz̃− ỹy − z̃y + y2) = Q(G)(ỹz̃− ỹy − z̃y + y2) + η̃2xv21 . . . v2n(ỹ2z̃2y0 − ỹ2z̃1y1 − ỹ1z̃2y1+ + ỹ1z̃1y2 − ỹ1z̃3 + ỹ1z̃2y1 + z̃3y1 − ỹ0z̃2y2) = Q′(G′) + η̃2xv 2 1 . . . v 2 n(ỹ 2z̃2y0 − ỹ2z̃1y1 − ỹ0z̃2y2) 288 Ars Math. Contemp. 21 (2021) #P2.08 / 283–299 Finally, when z = ỹ and vn+1 = z̃, respectively, we have {η1, η3} = {−1, 1} and η2 = 0. In the inverse case, when vn+1 = ỹ and z = z̃, there is {η1, η2} = {−1, 1} and η3 = 0. Therefore, in each case we have the desired form of the polynomial, thus completing the inductive argument. Recall that by Combinatorial Nullstellensatz, (i, j)-extendability of (G, x, y) can be expressed as the fact that there is a non-vanishing monomial in P (G) where exponents of x and y are i−1 and j−1, respectively, and every other exponent is less than 3. We obtain an analogue to Theorem 1.2 as the following Corollary 2.2. Let G be any 2-connected, outerplane near-triangulation with V (G) = {x, y, v1, . . . , vn}. Let C : V (G) → {1, 2, 3} be any proper 3-colouring of G. Then in the graph polynomial P (G) (i) there is no monomial of the form ηx0y0 ∏n i=1 v αi i with αi ≤ 2; (ii) the monomial of the form ηx1y0 ∏n i=1 v αi i with αi ≤ 2 does not vanish if and only if C(x) ̸= C(y); (iii) there is non-vanishing monomial of the form ηxβyγ ∏n i=1 v αi i with αi ≤ 2, β, γ ≤ 1. Proof. For the first point, simply note that outerplane near-triangulation on n + 2 vertices has 2n+ 1 edges, while the sum of the exponents of the given monomial is at most 2n. For the second point and for the third one: when x and y are adjacent one may apply Theorem 1.3 directly; otherwise, by the Hutchinson’s shrinking argument it is enough to verify an existence of a suitable monomial for G having exactly 2 vertices of degree 2, when x and y are these vertices. Indeed, suppose otherwise and consider any chord (inner edge) ab of G that separates the component H of the graph not containing vertices x and y. Such a chord exists, unless x and y are the only degree 2 vertices of G. Let G1 = G[V (G) \ V (H)] and G2 = G[V (H) ∪ {a, b}]. By Theorem 1.3 P (G2 − ab) contains non-vanishing monomial of the form s2 = ηa0b0vα11 . . . v αk k with αi ≤ 2. Note, that common variables in P (G1) and P (G2 − ab) are a and b only and that the sum of the exponents in any monomial in P (G2 − ab) is fixed. Hence, any other monomial in P (G2 − ab) has different exponents for some of v1, . . . vk. Therefore, as there is P (G) = P (G1)P (G2 − ab), G with x and y satisfies the second (or the third one, respectively) point of the corollary if and only if G1 with x and y does. Actually, the existence of desired monomials s in P (G) and s1 in P (G1), respectively, is equivalent by identity s = s1s2. Repeating the above argument until there is no separating chord one can shrink G to the claimed form. By Theorem 2.1 this finishes the proof of the third point as then one has either η1 ̸= 0 or η2 ̸= 0. For the second point it is enough to notice that under the assumption of Theorem 2.1 there is η1 = 0 if and only if C(x) = C(y). Note that there is also η3 = 0 if and only if C(z) = C(x) and then η2 = 0 if and only if x, y and z have 3 different colours. One may prove this fact by a simple analysis of the inductive step in the proof of Theorem 2.1. Indeed, in the base case (a triangle xyz) we have η2 = 0. Further, when G is extended to G′ by a triangle ỹz̃y then 1. η̃1 = 0 (C(ỹ) = C(x)) forces η3 = 0 (when z = ỹ) or η2 = 0 (when z = z̃), P. Gordinowicz and P. Twardowski: The polynomial method for list-colouring extendability . . . 289 2. η̃2 = 0 forces η1 = 0 (C(x) = C(y)), 3. η̃3 = 0 (C(z̃) = C(x)) forces η3 = 0 (when z = z̃) or η2 = 0 (when z = ỹ). 3 Poly-extendability of general outerplanar graphs The results of the previous section can be of course applied to any outerplanar graph, not necessarily triangulated. This, however, leads to loss of information, as usually there is more than one way to triangulate the graph, and different triangulations may lead to dif- ferent types of extendability. Moreover, in the case of non-triangulated graphs, as well as those that are not 2-connected, the counting argument behind point (i) of Corollary 2.2 does not work any more. Hence, it is possible for a general outerplanar graph to be (1, 1)- extendable. At first, a formal definition of fundamental subgraphs is provided, followed by three instrumental lemmas. Definition 3.1. Let G be a 2-connected outerplane graph, x, y ∈ V (G) and let T (G) be the weak dual of G. The fundamental x − y subgraph of G is the subgraph of G induced by the vertices belonging to faces that have vertices representing them in T (G) lying on the shortest path between vertices representing faces on which x and y lie. If xy ∈ E(G), then the fundamental subgraph reduces to an edge xy. Here, the assumption that the graph is outerplane is needed, as the construction of weak dual requires a particular embedding to be chosen. Notice however that in case of 2- connected outerplanar graphs there is, up to isomorphism, just one outerplane embedding, hence every 2-connected outerplanar graphs has essentially a single weak dual. Therefore in the rest of the paper we will assume the graphs to be outerplanar, as the choice of an embedding is irrelevant for our purpose. Definition 3.2. Let G be a connected outerplanar graph with cutvertices, and let BC(G) be the block-cutvertex graph of G. Let x, y ∈ V (G) be vertices lying in two different blocks of G. The fundamental x − y subgraph of G consists of all blocks that have ver- tices representing them in BC(G) lying on the shortest path between vertices representing blocks containing x and y, and each of those blocks is restricted to the fundamental a − b subgraph, where a, b ∈ V (G) are the two cutvertices belonging to the given block and to the shortest path between blocks containing x and y in BC(G). Definition 3.3. An outerplanar graph G with x, y ∈ V (G) is xy-fundamental if its fun- damental x − y subgraph is equal to G. An outerplanar graph G is fundamental if it is xy-fundamental for some x, y ∈ V (G). Lemma 3.4. Let G be a 2-connected xy-fundamental near-triangulation, such that C(x) = C(y), where C : V (G) → {1, 2, 3} is any proper 3-colouring of G. Let v0 be the vertex of G that has degree 2 in G − y, and v1, . . . , vn be the remaining vertices. Then in P (G) there is a non-vanishing monomial of the form ηx0y2v10v 2 1 . . . v 2 n, with η ∈ {−1, 1}. Proof. As C(x) = C(y), then C(x) ̸= C(v0). Hence by the second case of Corollary 2.2, there is a non-vanishing monomial ηx0v10v 2 1 . . . v 2 n, with η ∈ {−1, 1} in P (G−y). Adding y back, thus multiplying P (G − y) by (y − v0)(y − vn) = y2 − yv0 − yvn + v0vn, we get the monomial specified in the statement, and as it is the only way to obtain it, it is non-vanishing. 290 Ars Math. Contemp. 21 (2021) #P2.08 / 283–299 Figure 2: Top: a connected, outerplanar graph G; Bottom: a fundamental x − y subgraph of G. Lemma 3.5. Let G,G′ be any two graphs, such that V (G) = {x, v1, . . . , vn}, V (G′) = {x′, u1, . . . , um}. Let G′′ be the graph obtained from G and G′ by identifying x with x′, thus creating vertex x′′, and carrying neighbouring relations from G,G′. Suppose there are non-vanishing monomials ηxαΠvαii and η ′x′βΠu βj j in P (G) and P (G ′) respectively. Then in P (G′′) there is a non-vanishing monomial A(G′′) = ηη′x′′α+βΠvαii Πu βj j . Proof. As both η and η′ are non-zero, then the only way A(G′′) would vanish is that there were a monomial A′(G′′) = νν′x′′α ′+β′Πvαii Πu βj j , where νν ′ = −ηη′ and α′ + β′ = α + β. But then in P (G) and P (G′) there would have to be respective non-vanishing monomials νxα ′ Πvαii and ν ′x′β ′ Πu βj j , and as the sum of exponents in every monomial in a polynomial of given graph is fixed, we have that α = α′ and β = β′, a contradiction. Thus A(G′′) is non-vanishing. Lemma 3.6. Let G be a path of length n, n ≥ 2, where x, y are the endpoints and v1, . . . , vn−1 are the internal vertices of G. Then in P (G) there is a non-vanishing mono- mial of the form ηx0y0v21v 1 2 . . . v 1 n−1, where η ∈ {−1, 1}. Proof. Suppose at first that n = 2. Then P (G) = (x−v1)(y−v1) = xy−xv1−yv1+v21 , and the last monomial is the one fulfilling the assertion. Now suppose that the lemma holds for n = k − 1. Then in P (G), where G is a path xv1 . . . vk−1, there is a monomial ηx0v21v 1 2 . . . v 1 k−2v 0 k−1. Now adjoining vk to vk−1, thus multiplying P (G) by (vk−1 − vk) we obtain a monomial ηx0v21v 1 2 . . . v 1 k−2v 1 k−1v 0 k for path of length k, hence completing the induction. 3.1 Near-triangulations with cutvertices The following theorem is a polynomial analogue of [4, Theorem 5.3] that characterizes extendability of outerplanar near-triangulations with cutvertices. P. Gordinowicz and P. Twardowski: The polynomial method for list-colouring extendability . . . 291 Figure 3: Illustration for Lemma 3.5. Top: graphs G (left) and G′ (right); Bottom: graph G′′. Theorem 3.7. Let G be a fundamental x − y subgraph with cutvertices {v1, . . . , vj−1}, CV (G) = (x, v1, . . . , vj−1, y) be the sequence consisting of x, y and the cutvertices of G in order that they occur on any of the paths from x to y, and ui,k being the remaining vertices in the i-th block. Then in P (G): (i) there is a non-vanishing monomial of the form η1x1y1Πvαmm Πu βi,k i,k , αm, βi,k ≤ 2 if every vertex from CV (G) is in the same colour class; (ii) there is a non-vanishing monomial of the form η2x0y1Πvαmm Πu βi,k i,k , αm, βi,k ≤ 2 if there is a single pair of successive vertices in CV (G) that are in different colour classes; (iii) there is a non-vanishing monomial of the form η3x0y0Πvαmm Πu βi,k i,k , αm, βi,k ≤ 2 if there are at least two pairs of successive vertices in CV (G) that are in different colour classes; Figure 4: An example of labelling described in Theorem 3.7. 292 Ars Math. Contemp. 21 (2021) #P2.08 / 283–299 Proof. Start with partitioning G by its cutvertices into separate, 2-connected, vi−1vi-funda- mental outerplanar near-triangulations B1, . . . , Bj . To each of these graphs, Theorem 2.1 applies, and P (G) = P (B1) . . . P (Bj). If in each of those blocks the colour class of degree 2 vertices is the same, then in each of their polynomials there is a non-vanishing monomial such that exponents of degree 2 vertices are equal to 1, with other exponents no larger than 2. Thus case 1 is just a repeated use of Lemma 3.5. In the second case, let Bi be the block with degree 2 vertices in different colour classes. If i = 1, then in P (B1) there is a non-vanishing monomial of the form η0x0v11Πu 2 1,k. Hence again by Lemma 3.5 we get the desired monomial. If i > 1, then we apply Lemma 3.4 to each block B1 to Bi−1, thus by Lemma 3.5 obtaining monomial with x0 and v2i−1. As vi−1 and vi are in different colour classes, P (Bi) contains a non-vanishing monomial ηiv0i−1v 1 iΠu 2 i,k, hence through Lemma 3.5 we finish the case. The last case is starts analogously to the second one, with Bi, Bl, i < l being two blocks with endpoints in different colour classes. Let G′ be the vi−1vl-fundamental subgraph of G. By Theorem 2.1 there is a non-vanishing monomial in P (Bi) with v0i−1 and v 1 i and a monomial in P (Bl) with v1l−1 and v 0 l . As every block between Bi and Bl has a monomial with endpoints in power 1, by Lemmas 3.4 and 3.5 there is a monomial in P (G′) with both vi−1 and vl in power 0. Again by Lemmas 3.4 and 3.5 we can now adjoin remaining parts of G to G′, with their suitable monomials creating a desired monomial in P (G). 3.2 2-connected outerplanar graphs with non-triangular faces The following three theorems are jointly analogous to [4, Theorem 4.3]. Theorem 3.8. Let G be a 2-connected xy-fundamental graph with exactly one non-tri- angular interior face, and that face contains x and does not contain y. Let V (G) = {x, y, a, b, v1, . . . , vn}, where a, b are the two vertices of non-triangular face belonging to the neighbouring interior face. Let C(v) be the colour class of vertex v in the 3-colouring of the graph induced by all of the triangular faces. Then in P (G): (i) there is a non-vanishing monomial of the form η1x0y1aαabαbΠvαii , αk ≤ 2 if d(x, a) = 1 and C(a) = C(y) OR d(x, b) = 1 and C(b) = C(y); (ii) there is a non-vanishing monomial of the form η2x0y0aαabαbΠvαii , αk ≤ 2 other- wise. Proof. Suppose that d(x, a) = 1 and C(a) = C(y). Let G′ be the subgraph of G created by deleting all the vertices on the non-triangular face except for a and b. As G′ is an outerplanar near-triangulation Theorem 2.1 applies, and as C(a) = C(y), then in P (G′) there is a non-vanishing monomial with a1 and y1. If we now adjoin vertex x to a, creating graph G′′, then it P (G′′) there is a non-vanishing monomial with x0, a2 and y1. Now adding a path between x and b, thus reconstructing G (notice that the length of this path is at least 2, as the face is not a triangle), by Lemma 3.6 we obtain a desired monomial. The case when d(x, b) and C(b) = C(y) is handled analogously. If this is not the case, then either d(x, a) > 1 and d(x, b) > 1, or d(x, a) = 1 and C(a) ̸= C(y) (or analogously d(x, b) = 1 and C(b) ̸= C(y)). In the first case, then by Theorem 2.1 and Lemma 3.4 in P (G′) (with G′ defined as previously) there is a non- vanishing monomial with y0 and all other powers less than 3. Now as we join x with a and b with previously deleted paths, Lemma 3.6 gives us a monomial with x0, y0 and all other P. Gordinowicz and P. Twardowski: The polynomial method for list-colouring extendability . . . 293 Figure 5: Examples of labelling as in Theorem 3.8. Left: example to point (i); Right: example to point (ii). powers less than 3. In the second case, as C(a) ̸= C(y), by 2.1 there is a monomial in P (G′) where y has power 0 and a has power 1. Adjoining x to a, we obtain a monomial with x0, y0 and a2, and as we join x with b by a path, Lemma 3.6 gives us a desired monomial. Case when d(x, b) = 1 and C(b) ̸= C(y) is again analogous to the last one. Theorem 3.9. Let G be a 2-connected xy-fundamental graph with exactly one non-trian- gular interior face, and that face does not contain x nor y. Let V (G) = {x, y, a, b, c, v1, . . . , vn}, where a, b and a, c are the two pairs of vertices of non-triangular face belonging to the neighbouring interior faces, and let C(v) be the colour class of vertex v in the 3- colouring of the subgraph of G created by deleting the path connecting b and c. Then in P (G): (i) there is a non-vanishing monomial of the form η1x1y1aαabαbcαcΠvαii , αk ≤ 2, if C(x) = C(a) = C(y); (ii) there is a non-vanishing monomial of the form η2x0y1aαabαbcαcΠvαii , αk ≤ 2, if C(x) ̸= C(a) = C(y) or C(x) = C(a) ̸= C(y); (iii) there is a non-vanishing monomial of the form η3x0y0aαabαbcαcΠvαii , αk ≤ 2, if C(x) ̸= C(a) ̸= C(y); Proof. Let G′ be the subgraph of G obtained by deleting path connecting b and c from G. Obviously G′ is an outerplanar near-triangulation with a single cutvertex a, hence Theo- rem 3.7 applies to it. Notice moreover, that the first case of the above theorem leads to the first case of Theorem 3.7, and the second and third case also relate similarly. As Theo- rem 3.7 gives us suitable monomials, when we add back the path we previously deleted, an application of Lemma 3.6 finishes the proof. Theorem 3.10. Let G be a 2-connected xy-fundamental graph with exactly one non- triangular interior face, and that face does not contain x nor y. Let V (G) = {x, y, a, b, c, d, v1, . . . , vn}, where a, b and c, d are the two pairs of vertices of the non-triangular face be- longing to the neighbouring interior faces with ab ∈ E(G) and cd ∈ E(G), and let C(v) be the colour class of vertex v in the 3-colouring of the subgraphs of G created by deleting the paths connecting a with c and b with d. Then in P (G): 294 Ars Math. Contemp. 21 (2021) #P2.08 / 283–299 Figure 6: An example of labelling described in Theorem 3.9. (i) there is a non-vanishing monomial of the form η1x0y1aαabαbcαcdαdΠvαii , αk ≤ 2, if d(a, c) = 1, C(x) = C(a) and C(y) = C(c) OR d(b, d) = 1, C(x) = C(b) and C(y) = C(d); (ii) there is a non-vanishing monomial of the form η2x0y0aαabαbcαcdαdΠvαii , αk ≤ 2 otherwise; Figure 7: An example of labelling described in Theorem 3.10. Proof. Suppose at first that C(x) = C(a) and C(y) = C(c). We can connect vertex a with d, and if d(b, d) > 1, also with every interior vertex on the path connecting b with d, thus obtaining an xy-fundamental 2-connected near triangulation G′. If d(a, c) = 1, then C(a) ̸= C(c), thus C(x) ̸= C(y), and by Corollary 2.2 P (G′) contains a non- vanishing monomial with x0, y1 and every other exponent equals 2. As neither x nor y were affected by addition of edges to G, P (G) contains a non-vanishing monomial of the form η1x0y1aαabαbcαcdαdΠvαii , αk ≤ 2. If d(a, c) > 1, then G′ fulfils the conditions of Theorem 3.9, with d serving as vertex a in the statement of that theorem. Moreover, as C(x) = C(a) and C(y) = C(c), and d neighbours both a and c in G′, then in colouring of G′ C(x) ̸= C(d) and C(y) ̸= C(d). Hence by Theorem 3.9 P (G′) contains a non- vanishing monomial with x0, y0 and every other exponent no larger than 2, and this again P. Gordinowicz and P. Twardowski: The polynomial method for list-colouring extendability . . . 295 implies that there is a non-vanishing monomial of the form η2x0y0aαabαbcαcdαdΠvαii , αk ≤ 2 in P (G). The case when C(x) = C(b) and C(y) = C(d) is analogous. Suppose now that C(x) ̸= C(a) and C(y) = C(c). Start by removing the paths from a to c and b to d from G. This leaves us with two separate, 2-connected near triangu- lations G′ and G′′ with {x, a, b} ∈ V (G′) and {y, c, d} ∈ V (G′′). As C(y) = C(c), then C(y) ̸= C(d), and by Corollary 2.2 in P (G′′) there is a non-vanishing monomial of the form η1y0d1c2Πv2i . Now as C(x) ̸= C(a), there exists a non-vanishing monomial η1x 0a1b2Πu2i in P (G ′), as the polynomial of xa-fundamental subgraph of G′ contains a non-vanishing monomial with x0 and a1, and as G′ is a 2-connected near triangulation, every other exponent must be equal to 2. Now add back the previously removed paths. Each of them contains in its graph polynomial a non-vanishing monomial with every ex- ponent equal to 1, except for one of its endpoints, which has power 0. We will call that monomial oriented towards the endpoint with non-zero exponent. Add paths connecting a with c and b with d to G′ and G′′, and by multiplication of the monomials described above we obtain a monomial of the form η2x0y0aαabαbcαcdαdΠvαii , αk ≤ 2 in P (G), where exponent of each of the vertices a, b, c, d is equal to 2. This monomial does not vanish, as the only other way to get this monomial would require us to orient both of the paths in the opposite direction, but this would imply that there were a non-vanishing monomial η1y 0d2c1Πv2i in P (G ′′), which is not the case as C(y) = C(c). Cases where C(x) = C(a) and C(y) ̸= C(c), C(x) ̸= C(b) and C(y) = C(d) or C(x) = C(b) and C(y) ̸= C(d) are sorted out in the same manner. The last case is when C(x) ̸= C(a) and C(y) ̸= C(c). Observe at first, that we can also assume that C(x) ̸= C(b) and C(y) ̸= C(d), as all the other cases were already solved in previous arguments due to symmetries. Let G′ and G′′ be as in previous case. As C(b) ̸= C(x) ̸= C(a), then in P (G′) there are non-vanishing monomials η1x0a1b2Πv2i and −η1x0a2b1Πv2i . Similarly, there are non-vanishing monomials η2y0c1d2Πu2i and −η2y0c2d1Πu2i in P (G′′). Now reconstruct G as previously, orienting path connecting a and c towards a and path connecting b and d towards d. To comply with requirements of the assertion, we have to use the first and fourth monomial from those specified above, thus in P (G) we have a monomial −η1η2x0y0a2b2c2d2Πv2i . The only other way to reach this set of exponents is to use the second and third monomial, and orient paths in opposite directions, but as a simultaneous switch of orientations preserves sign, we again obtain −η1η2x0y0a2b2c2d2Πv2i , so those monomials do not annihilate each other, but rather dou- ble the coefficient. As all cases are now addressed, the proof is complete. 3.3 General outerplanar graphs The three theorems above can be combined with Theorem 3.7 to obtain a general character- isation of (i, j)-extendability of outerplanar graphs. We will start with some technicalities. Definition 3.11. Let G be an outerplanar graph. A non-triangular inner face of G will be called type 0 if it is as defined in Theorem 3.8 (with possibly y belonging to that face instead of x), type 1 if it is as defined in Theorem 3.9 and type 2 if it is as defined in Theorem 3.10. In case of type 1 faces, the vertex belonging to the two neighbouring faces will be called an apex of that face. Lemma 3.12. Let G be a connected outerplanar graph with V (G) = {x, y, v1, . . . , vi} and let G′ be a supergraph of G obtained by adding a path of the length 2 to G in a way that preserves outerplanarity. Then the monomial xαxyαyΠvαii does not vanish in P (G) if 296 Ars Math. Contemp. 21 (2021) #P2.08 / 283–299 and only if the monomial xαxyαyΠvαii z 2 does not vanish in P (G′), where z is the middle vertex of the added path. Proof. The implication from P (G) to P (G′) is obvious and was shown to be true and uti- lized multiple times in this paper. Suppose there is a non-vanishing monomial xαxyαyΠvαii z 2 in P (G′). As P (G′) = P (G)(ab−az−bz+z2), where a, b are the endpoints of the added path, and none of the monomials from P (G) contains z due to the fact that z /∈ V (G), then the only way to obtain the monomial above is by multiplying xαxyαyΠvαii by z 2, thus the former must occur in P (G). Definition 3.13. Let G be a 1-connected fundamental outerplanar graph. For every cutver- tex of G that is not an endpoint of any bridge add a path of length 2, connecting the pair of some neighbours of that cutvertex without disrupting outerplanarity, thus creating a non- triangular face of type 0. Then for every bridge or chain of bridges of G add a path of the length 2 connected to the pair of the neighbours of the endpoints of that bridge or chain of bridges (or to the neighbour and the endpoint if it has degree 1) in a way that preserves outerplanarity, creating a face of type 2 (or type 0). Finally, if G is a path, connect end- points of that path with a path of length 2. The resulting supergraph of G will be called a 2-connection of G. The 2-connection of A 2-connected graph would be the graph itself. Notice, that the 2-connection of a 1-connected graph is not unique — for example, the graph on Figure 8 has 8 different 2-connections. However, each of the 2-connections has the same relevant properties — namely the color classes of the cutvertices and types of the newly created non-triangular faces. Figure 8: Top: a connected, outerplanar graph G; Bottom: a possible 2-connection of G. The following remark is a direct consequence of Lemma 3.12. Remark 3.14. Let G be a connected xy-fundamental outerplanar graph, V (G) = {x, y, v1, . . . , vm} and let G′ be its 2-connection, V (G′) = {x, y, v1, . . . , vm, u1, . . . , un}. There is a non-vanishing monomial xαxyαyΠvαii in P (G) if and only if there is a non-vanishing monomial xαxyαyΠvαii Πu 2 j in P (G ′). P. Gordinowicz and P. Twardowski: The polynomial method for list-colouring extendability . . . 297 The following theorem presents a full characterisation of the polynomial extendability of connected fundamental outerplanar graphs. Theorem 3.15. Let G be a connected xy-fundamental outerplanar graph, V (G) = {x, y, v1, . . . , vi}, and let G′ be a 2-connection of G. Then in P (G): (i) there is a non-vanishing monomial of the form x1y1Πvαii , αk ≤ 2 if G is a 2- connected near-triangulation with C(x) = C(y) OR G is as in point 1 of Theo- rem 3.7 OR every non-triangular face of G′ is of type 1 and every apex, x and y have the same colour in every 3-colouring of G. (ii) there is a non-vanishing monomial of the form x0y1Πvαii , αk ≤ 2 if G is a 2- connected near-triangulation with C(x) ̸= C(y) OR G is as in point 2 of Theo- rem 3.7 OR G′ is as in point 1 of Theorem 3.8 OR G′ is as in point 1 of Theorem 3.10 OR every non-triangular face of G′ is of type 1 and in every 3-colouring of G′ there is exactly one pair of consecutive apexes (or either x or y with the closest apex) with different colours OR only one of the non-triangular faces of G′ is not of the type 1 and conditions of point 1 of Theorem 3.10 are fulfilled on that face. (iii) there is a non-vanishing monomial of the form x0y0Πvαii , αk ≤ 2 otherwise. Proof. We will omit every case that is covered already by previous theorems, leaving us only with the cases when there are multiple non-triangular faces. Suppose all of those are of type 1. It is easy to see (with some help of Lemma 3.6) that for every such face removal of all vertices belonging only to this (and outer) face produces a cutvertex, simultaneously changing nothing in terms of extendability-relevant monomials. Hence apply Theorem 3.7, with each apex acting as a cutvertex. Suppose now there is a face of type either 0 or 2 in G′. Theorems 3.8 and 3.10 show that the only cases where there is no monomial in P (G′) (and thus in P (G)) with both x and y in power 0 is when 3-colouring G′ we cannot avoid a situation described in point 1 of either of these theorems on any of such faces, and in those cases there is a non-vanishing monomial with x0 and y1. Observe that this is not the case when there are at least two faces of type 0 or 2, as we can avoid this situation by either permuting the colours, or by changing them on vertices of degree 2 (as in case of type 0 faces at least one such vertex other than x and y definitely exists). So there are only two cases when we cannot avoid that. The first is when in G′ there is only one face of type 2, no faces of type 0, there is a pair of neighbouring vertices belonging to this face such that the only other face of G′ they belong to simultaneously is the outer face, and in any 3-colouring of G (and thus also G′) each of those vertices has the same colour as x or y, depending on which of those vertices lies on the same ”side” of that face. Label the vertex from this pair lying closer to x as vx, and the one being closer to y as vy . The case of C(x) = C(vx) can occur either when on one side there are only triangular faces between x and vx, with the structure of that triangulation forcing the same colour of those vertices, or when for every type 1 face between those vertices, the triangular structure between neighbouring faces or between x (or vx) and the nearest such face forces the same colour on each of those vertices. The same is true for y and vy , with the restriction that the former situation cannot occur for both of those pairs. The second case is when there is exactly one face of type 0 in G′ (without loss of generality we can assume that x lies on that face), no faces of type 2, x has a neighbour (v0) that lies also on adjacent inner face, and the colour of that vertex is the same as colour 298 Ars Math. Contemp. 21 (2021) #P2.08 / 283–299 of y in every 3-colouring of G′. This can be only caused by the fact that the apex of every type 1 face is forced to have the same colour as the others, as well as y and v0. Finally, we prove that Theorem 3.15 can be restated as Theorem 1.4. Proof of Theorem 1.4. Neither the graph polynomial nor the colouring depends on a partic- ular graph embedding. Therefore, let G be any outerplanar graph with V (G) = {x, y, v1, . . . , vn}. At first notice, that if G is not connected and x and y are in different connected components, one may use Theorem 1.3 directly to obtain a monomial with β = γ = 0, so then obviously the third case occurs. For x and y in one component observe that by the Hutchinson’s shrinking argument it is enough to prove theorem for G being xy-fundamental graph. See the proof of Corollary 2.2 for details. Now consider consequences of each of the situations described in the statement of Theorem 3.15 in terms of 3-colourings. In every case of point (i) we obviously have that C(x) = C(y). Moving to the second point, the first condition again directly states that C(x) ̸= C(y). If G is as in point 2 of Theorem 3.7 or every non-triangular face of G′ is of type 1 and in every 3-colouring of G′ there is exactly one pair of consecutive apexes (or either x or y with the closest apex) with different colours, as the colour class changes only once on the cutvertices/apexes, then obviously classes of terminal vertices x and y have to be different. If G′ is as in point 1 of Theorem 3.8, then it is directly stated that the colour of one of terminal vertices is the same as the colour of one of the neighbours of the other terminal vertex, thus the colours of terminal vertices have to be different. Finally, if G′ is as in point 1 of Theorem 3.10 or only one of the non-triangular faces of G′ is not of the type 1 and the conditions of point 1 of Theorem 3.10 are fulfilled on that face, the vertices x and y are in the same colour class as vertices a and c (or b and d), respectively, and those vertices are adjacent, hence their colours cannot possibly be the same. Finally, observe that in any other case the colour classes of x and y are independent — the structure of the graph permits the colours to be rearranged in some parts without changing the colours in the other parts, therefore the graph can be properly 3-coloured with both C(x) = C(y) and C(x) ̸= C(y). As an example consider point (ii) of Theorem 3.8, other cases are analogous. Starting with the triangulated part of the graph (i.e. the graph minus internal vertices of the path between a and b containing x) already coloured, analyse possible proper 3-colourings of the path from a to b. If min(d(x, a), d(x, b)) > 1, then we can colour x with any of the 3 colours. Otherwise, suppose without loss of generality that d(x, a) = 1 and hence d(x, b) > 1. Then x can be coloured with any colour except C(a), but there is C(a) ̸= C(y). Therefore, again x can get colour of y or some different one. 4 Further work Extendability is naturally transformed into plane graphs by allowing interior vertices to have a list of colours of length 5. In [5] and [6] Postle and Thomas provided results that may be summarized in the following theorem. Theorem 4.1. Let G = (V,E) be any plane graph, let C ⊆ V be the set of vertices on the outer face, x, y ∈ C, x ̸= y. Then (i) (G, x, y) is (1, 2)-extendable if and only if there exists a proper colouring c : C → {1, 2, 3} such that c(x) ̸= c(y); P. Gordinowicz and P. Twardowski: The polynomial method for list-colouring extendability . . . 299 (ii) (G, x, y) is (2, 2)-extendable. One may ask, whether is it possible to restate the above theorem in the terms of a graph polynomial, i.e. to extend, at least partially Theorem 1.4 to planar graphs. Our partial results suggest that it is possible. ORCID iDs Przemysław Gordinowicz https://orcid.org/0000-0001-9843-3928 Paweł Twardowski https://orcid.org/0000-0003-1259-4830 References [1] N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput. 8 (1999), 7–29, doi:10. 1017/s0963548398003411, recent trends in combinatorics (Mátraháza, 1995). [2] N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), 125– 134, doi:10.1007/bf01204715. [3] J. Grytczuk and X. Zhu, The Alon-Tarsi number of a planar graph minus a matching, J. Combin. Theory Ser. B 145 (2020), 511–520, doi:10.1016/j.jctb.2020.02.005. [4] J. P. Hutchinson, On list-coloring extendable outerplanar graphs, Ars Math. Contemp. 5 (2012), 171–184, doi:10.26493/1855-3974.179.189. [5] L. Postle and R. Thomas, Five-list-coloring graphs on surfaces I. Two lists of size two in planar graphs, J. Combin. Theory Ser. B 111 (2015), 234–241, doi:10.1016/j.jctb.2014.08.003. [6] L. Postle and R. Thomas, Five-list-coloring graphs on surfaces III. one list of size one and one list of size two, J. Combin. Theory Ser. B 128 (2018), 1–16, doi:10.1016/j.jctb.2017.06.004. [7] U. Schauz, Mr. Paint and Mrs. Correct, Electron. J. Combin. 16 (2009), Research Paper 77, 18, doi:10.37236/166. [8] C. Thomassen, Every planar graph is 5-choosable, J. Combin. Theory Ser. B 62 (1994), 180– 181, doi:10.1006/jctb.1994.1062. [9] D. B. West, Introduction to Graph Theory, 2nd edition, Prentice Hall, Inc., Upper Saddle River, NJ, 2001, https://faculty.math.illinois.edu/˜west/igt/. [10] X. Zhu, The Alon-Tarsi number of planar graphs, J. Combin. Theory Ser. B 134 (2019), 354– 358, doi:10.1016/j.jctb.2018.06.004.