Graph polynomials and group coloring of graphs

Eu opean Jou nal o Combina o ics 102 (2022) 103505 Con en s lis s a ailable a ScienceDi ec Eu opean Jou nal o Combina o ics jou nal homepage: www.else ie .com/loca e/ejc G aph polynomials and g oup colo ing o g aphs✩ Ba łomiej Boseka, Ja osław G y czukb, G zego z Gu owskia, O iol Se ac, Ma iusz Zającb aIns i u e o Theo e ical Compu e Science, Facul y o Ma hema ics and Compu e Science, Jagiellonian Uni e si y, K aków, Poland bFacul y o Ma hema ics and In o ma ion Science, Wa saw Uni e si y o Technology, Wa saw, Poland cDepa men o Ma hema ics, Uni e si a Poli ècnica de Ca alunya, Ba celona, Spain a icle in o A icle his o y: Recei ed 13 Feb ua y 2021 Accep ed 15 Decembe 2021 A ailable online 12 Janua y 2022 abs ac Le Γbe an Abelian g oup and le Gbe a simple g aph. We say ha Gis Γ-colo able i o some ixed o ien a ion o Gand e e y edge labeling ℓ:E(G)→Γ, he e exis s a e ex colo ing cby he elemen s o Γsuch ha c(y)−c(x)= ℓ(e), o e e y edge e=xy (o ien ed om x o y). Langhede and Thomassen p o ed ecen ly ha e e y plana g aph on n e ices has a leas 2n/9di e en Z5-colo ings. By using a di e en app oach based on g aph polynomials, we ex end his esul o K5-mino - ee g aphs in he mo e gene al se ing o ield colo ing. Mo e speci ically, we p o e ha e e y such g aph on n e ices is F-5-choosable, whene e Fis an a bi a y ield wi h a leas 5 elemen s. Mo eo e , he numbe o colo ings ( o e e y lis assignmen ) is a leas 5n/4. ©2022TheAu ho s.PublishedbyElse ie L d.Thisisanopen accessa icleunde heCCBY-NC-NDlicense (h p://c ea i ecommons.o g/licenses/by-nc-nd/4.0/). 1. In oduc ion Le Γbe an Abelian g oup and le Gbe a simple g aph. We say ha Gis Γ-colo able i o some o ien a ion o Gand e e y edge labeling ℓby he elemen s o Γ he e exis s a e ex colo ing cby ✩Suppo ed by he Polish Na ional Science Cen e , G an Numbe : NCN 2019/35/B/ST6/02472. O iol Se a acknowledges inancial suppo om he Spanish Agencia Es a al de In es igación unde p ojec MTM2017-82166-P. E-mail add esses: [email p o ec ed] (B. Bosek), [email p o ec ed] (J. G y czuk), [email p o ec ed] (G. Gu owski), [email p o ec ed] (O. Se a), [email p o ec ed] (M. Zając). h ps://doi.o g/10.1016/j.ejc.2021.103505 0195-6698/©2022 The Au ho s. Published by Else ie L d. This is an open access a icle unde he CC BY-NC-ND license (h p://c ea i ecommons.o g/licenses/by-nc-nd/4.0/). B. Bosek, J. G y czuk, G. Gu owski e al. Eu opean Jou nal o Combina o ics 102 (2022) 103505 he elemen s o Γsuch ha c(y)−c(x)= ℓ(e), o e e y edge e=xy (o ien ed om x owa ds y). This no ion was in oduced by Jaege , Linial, Payane and Ta si [9] as a dual concep o g oup connec i i y. Answe ing a ques ion posed in [9], Lai and Zhang [11] p o ed ha e e y plana g aph is Z5- colo able. Recen ly, Langhede and Thomassen [12] s eng hened his esul by p o ing ha he numbe o Z5-colo ings o e e y plana g aph on n e ices ( o any ixed edge labeling) is a leas 2n/9. The p oo is elemen a y bu qui e in ol ed. In his pape we u he ex end hese esul s by using he polynomial me hod. I is con enien o in oduce a sligh ly mo e gene al se ing. Le Fbe an a bi a y ield and le Gbe a simple g aph. Suppose ha each edge e=xy o Gis assigned a iple (ae,be,ce)∈F3, wi h ae,be= 0. We say ha Gis F-colo able i o e e y such edge labeling he e exis s a e ex colo ing by he elemen s o F such ha ae (x)+be (y)+ce= 0, o e e y edge e=xy. Clea ly, F-colo abili y o a g aph implies i s Γ-colo abili y, whe e Γis he addi i e g oup o he ield F. De ine a g aph G o be F-k-choosable i i is F-colo able om a bi a y lis s o elemen s o F, each o size k, assigned o he e ices. Theo em 1. Le G be a g aph on n e ices wi hou a mino o K5. Le Fbe an a bi a y ield wi h a leas 5elemen s. Then G is F-5-choosable. Mo eo e , he numbe o colo ings ( o any ixed lis assignmen and any ixed edge labeling) is a leas 5n/4. The p oo is based on he me hod o g aph polynomials. We use wo ools, he Combina o ial Nulls ellensa z o Alon [2] and a esul o Alon and Fü edi [3] conce ning he numbe o non-ze o alues o a polynomial e alua ed a all poin s o a mul idimensional g id. No ice ha Theo em 1 only co e s Abelian g oups ha a e addi i e g oups o a ield. Fo a gene al Abelian g oup Γo o de a leas 5, Chuang, Lai, Omidi, Wang, and Zake i p o ed in [6] by elemen a y me hods ha e e y K5-mino ee g aph is Γ-5-choosable. Theo em 1 does no ex end his esul , bu in he o e lapping cases gua an ees a s onge conclusion, and also easily implies i in he case o a bi a y cyclic g oups Γ(Theo em 10). 2. The esul s 2.1. G aph polynomials Le Gbe a simple g aph on he se o e ices V(G)= {x1,x2,...,xn}. Le PGbe he g aph polynomial o G, de ined by PG(x1,x2,...,xn)=∏ xixj∈E(G),i<j (xi−xj).(2.1) We iden i y symbols deno ing e ices o Gwi h a iables o PG. We may conside PGas a polynomial o e an a bi a y ield F. In he p ocess o expanding he polynomial PG, one c ea es monomials by picking one a iable om each ac o (xi−xj). Thus, e e y monomial co esponds o he unique o ien a ion o Gob ained by di ec ing he edge xixj owa ds he picked a iable. Thus, he deg ees o he a iables in he monomial coincide wi h he in-deg ees o he e ices in he co esponding o ien a ion. Le MGdeno e he mul i-se o all monomials a ising in his way. So, he ca dinali y o MGis equal o 2m, whe e m= |E(G)|, and he mul iplici y o each monomial Mis equal o he numbe o o ien a ions o Gsha ing he same in-deg ee sequence (co esponding o he deg ees o he a iables in M). The sign o a monomial M∈MGis he p oduc o signs o all a iables picked o o m M. The coe icien o a monomial Min PG, deno ed as cM(PG), is he sum o signs o all copies o Min MG. A monomial Mis called non- anishing in PGi cM(PG)= 0. Suppose now ha each edge e=xixjo a g aph G(o ien ed so ha i<j) is assigned an a bi a y pai (ae,be) o non-ze o elemen s o F. We say ha he edges o Ga e deco a ed wi h pai s (a,b), and we de ine he co esponding deco a ed g aph polynomial DGin which e e y ac o (xi−xj) co esponding o he edge e=xixjdeco a ed wi h (ae,be) is subs i u ed wi h (aexi+bexj): DG(x1,x2,...,xn)=∏ e=xixj∈E(G),i<j (aexi+bexj).(2.2) 2 B. Bosek, J. G y czuk, G. Gu owski e al. Eu opean Jou nal o Combina o ics 102 (2022) 103505 O cou se, di e en deco a ions may gi e di e en polynomials, bu we deno e he whole amily o hem wi h he same symbol DG, hoping ha his ambigui y will no cause oo much con usion. 2.2. Combina o ial Nulls ellensa z Fo a monomial M, le degxi(M) deno e he deg ee o he a iable xiin M. The o al deg ee o he monomial Mis he sum ∑n i=1degxi(M). In a g aph polynomial each monomial has he same o al deg ee equal o he numbe o edges o G. Recall ha he deg ee o a polynomial is he maximum o o al deg ees o i s non- anishing monomials. We will use he ollowing amous heo em o Alon [2]. Theo em 2 (Combina o ial Nulls ellensa z, [2]).Le P be a polynomial in F[x1,x2,...,xn], whe e Fis an a bi a y ield o coe icien s. Suppose ha he e is a non- anishing monomial xk1 1xk2 2···xkn nin P whose o al deg ee is equal o he deg ee o P. Then, o a bi a y se s Ai⊆F, wi h |Ai| = ki+1, he e exis elemen s ai∈Aisuch ha P(a1,a2,...,an)= 0. In iew o his heo em i is con enien o deno e by AF(P) he leas in ege ksuch ha he polynomial Phas a non- anishing monomial Mwhose deg ee is equal o he deg ee o Pand sa is ying degxi(M)⩽k, o each i=1,2,...,n. Le D1,D2be any wo o ien a ions o he g aph Gsha ing he same in-deg ee sequence. Obse e ha he se o edges o ien ed di e en ly in D1 han in D2is an Eule ian subg aph o bo h D1and D2. Thus, e e y monomial co esponding o an acyclic o ien a ion o Gis o mul iplici y exac ly 1 in MG. Such monomials a e non- anishing in PG, and AF(PG) is well de ined o e e y g aph G. Fo he deco a ed g aph polynomial DG, which deno es a collec ion o polynomials, we de ine AF(DG) as he leas numbe ksuch ha AF(P)⩽kholds o e e y Pin DG. I is no ha d o demons a e ha o e e y g aph Gwe ha e AF(PG)⩽AF(DG)⩽col(G)−1, whe e col(G) is he colo ing numbe o G, de ined as he leas ksuch ha he e ices o Gcan be linea ly o de ed so ha each e ex has a mos k−1 neighbo s ha p ecede in he o de ing. 2.3. Field colo ing and g aph polynomials Le Fbe any ield and le ℓbe any edge labeling o a g aph Gby he elemen s o F. Le DGbe a deco a ed g aph polynomial wi h some ixed deco a ion o e F. Conside he polynomial DG,ℓ de ined as: DG,ℓ(x1,x2,...,xn)=∏ e=xixj∈E(G) (aexi+bexj+ℓ(e)).(2.3) Ou basic obse a ion is o mula ed as ollows. Theo em 3. Le G be any simple g aph, wi h a g aph polynomial PG, and le Fbe an a bi a y ield. Le ℓbe any edge labeling o G by he elemen s o F. Then AF(DG,ℓ)=AF(DG). P oo . Fi s no ice ha he polynomial DG,ℓ can be w i en as: DG,ℓ =DG+Q,(2.4) whe e Qis a polynomial o deg ee s ic ly smalle han he deg ee o DG. Indeed, we ob ain he summand DGby choosing he whole exp ession (aexi+bexj) in e e y ac o o DG,ℓ. In e e y o he case, he o med monomial uses a leas one cons an ℓ(e), hence he o al deg ee o such monomial is s ic ly smalle han he numbe o edges o G, which is equal o he deg ee o DG. This means ha e e y non- anishing monomial o DGdoes no anish in DG,ℓ. This comple es he p oo . □ 3 B. Bosek, J. G y czuk, G. Gu owski e al. Eu opean Jou nal o Combina o ics 102 (2022) 103505 2.4. Field colo ing o plana g aphs In [21] Zhu p o ed ha e e y plana g aph Gsa is ies AQ(PG)⩽4, hough he same p oo wo ks o an a bi a y ield. This cons i u es an algeb aic analog o he amous esul o Thomassen [16] on 5-choosabili y o plana g aphs. We will de i e below a sligh ly s onge s a emen . Theo em 4. Le G be a plana g aph and le DGbe i s deco a ed g aph polynomial o e an a bi a y ield F. Then AF(DG)⩽4. By Theo ems 3 and 4we ge immedia ely he ollowing esul . Co olla y 1. E e y plana g aph is F-5-choosable, whe e Fis an a bi a y ield wi h a leas 5elemen s. The o iginal p oo om [21] is by induc ion wi h he same scena io as in Thomassen’s amous p oo om [16], excep o one unexpec ed wis . We will gi e below a pu ely algeb aic p oo along simila lines o he ollowing mo e gene al s a emen , s essing he ac ha i wo ks o deco a ed polynomials o e an a bi a y ield (which is c ucial o ou applica ions). Theo em 5. Le G be a nea - iangula ion and le e =xy be an a bi a y edge o he bounda y cycle o G. Then a deco a ed g aph polynomial DG−eo e an a bi a y ield Fcon ains a non- anishing monomial M sa is ying he ollowing condi ions: (i) degx(M)=degy(M)=0, (ii) deg (M)⩽2, o e e y bounda y e ex , (iii) degu(M)⩽4, o e e y in e io e ex u. Be o e we p esen he p oo , le us commen on how Theo em 4 is de i ed om Theo em 5. We can choose any plana d awing o a plana g aph G, and any edge e=xy o he bounda y cycle o he d awing. Le Mbe he non- anishing monomial in DG−egi en by Theo em 5, and obse e ha he monomial Mx does no anish in DGand ce i ies ha AF(DG)≤4. P oo o Theo em 5.Le us deno e P=DG−e, and call a non- anishing monomial Min Psa is ying condi ions (i)–(iii), a nice monomial o (G,e). We use induc ion on he numbe o e ices o G. I is easy o check ha G=K3, a comple e g aph on e ex se {x,y, }, sa is ies he asse ion. In his case we ha e DG−e=(a1x+b1 )(a2y+b2 ), and he only nice monomial is M= 2, whose coe icien is b1b2= 0. Hence, Mis non- anishing. We dis inguish wo cases. Case 1. The bounda y cycle o Ghas a cho d. Suppose i s ha Ghas a cho d =wz. This cho d spli s Gin o wo subg aphs G1and G2. We assume ha eis in G1, while belongs o bo h subg aphs. By induc ion we assume ha bo h g aphs con ain nice non- anishing monomials M1and M2 o (G1,e) and (G2, ), espec i ely. Le us deno e P1=DG1−e, and P2=DG2− . Then we ha e P=P1P2, and we see ha he monomial M=M1M2appea s in he expansion o P. We claim ha Mis a nice monomial o (G,e). I is easy o see ha Msa is ies condi ions (i)–(iii). To see ha i is non- anishing, no ice ha M=M1M2 is he only way o exp essing he monomial Mas a p oduc o wo monomials om P1and P2, espec i ely. This is because he only common a iables o P1and P2a e wand z, and hey do no occu in M2. This shows ha cM(P)=cM1(P1)·cM2(P2)= 0, con i ming ha Mis non- anishing in he polynomial P. 4 B. Bosek, J. G y czuk, G. Gu owski e al. Eu opean Jou nal o Combina o ics 102 (2022) 103505 Case 2. The bounda y cycle o Ghas no cho d. Suppose ha he e is no cho d in G. Le = xbe he neighbo o yon he bounda y o G. Le be he o he neighbo o on he ou e ace, and le x1,x2,...,xkbe he neighbo s o lying in he in e io o G. Le G′=G− . By he induc i e assump ion, he e is a nice monomial M′ o (G′,e) in he g aph polynomial P′=DG′−e. So, we ha e cM′(P′)= 0. Subcase 1. The bounda y ace is a iangle. Suppose i s ha =x, which means ha he bounda y ace is a iangle. In his case he nice monomial M′has he o m M′=Yx 1 1x 2 2. . . x k k, whe e i⩽2 o each i=1,2,...,k, and Yis a monomial consis ing o he es o he a iables. Since M′is nice o (G′,e), he monomial Ydoes no con ain a iables xand y, and each o he a iable zin Ysa is ies degz(Y)⩽4. Fi s no ice ha P=P′Q, whe e Q=(a +bx)(c +dy)(a1 +b1x1)(a2 +b2x2). . . (ak +bkxk). In he expansion o Qwe ge he monomial N= 2x1. . . xk, whose coe icien is cN(Q)=acb1···bk= 0. Hence, in he expansion o he p oduc P′Qwe ge he monomial M=M′N, which can be w i en as M=Yx 1+1 1x 2+1 2. . . x k+1 k 2. Clea ly Msa is ies condi ions (i)–(iii). We claim ha i is also non- anishing in P. Mo e speci ically, we claim ha he e is only one way o exp essing Mas a p oduc M=AB o wo monomials, wi h A om P′and B om Q. Indeed, o ge 2in Bwe ha e o use he i s wo ac o s o Q, since o he wise we ha e xo yin M. This implies ha B=Nand A=M′. Thus cM(P)=cM′(P′)·cN(Q)= 0, which shows ha Mis non- anishing in P. Fo he emaining subcases, we assume ha = x. Subcase 2. The e is a special monomial. Suppose i s ha he e exis s a non- anishing special monomial Sin P′which sa is ies all condi ions (i)–(iii), excep ha deg (S)⩽1 and degxi(S)⩽3 o a mos one i. We may assume wi hou loss o gene ali y ha i=1. So, we assume ha cS(P′)= 0. This special monomial Scan be w i en in he o m S=Zxs1 1xs2 2. . . xsk k s, whe e s⩽1, s1⩽3, si⩽2 o i=2,3, . . . k, and Zis some monomial consis ing o he es o he a iables. As be o e we may w i e he polynomial P=DG−eas he p oduc P=P′Qwi h Q=(a +by)(c +d )(a1 +b1x1). . . (ak +bkxk). In he expansion o Qwe ge he monomial N′= x1. . . xk, wi h coe icien cN′(Q)=adb1···bk= 0. Hence, in he expansion o he p oduc P′Qwe ge he monomial M=SN′, which can be w i en as M=Zxs1+1 1xs2+1 2. . . xsk+1 k s+1 . 5 B. Bosek, J. G y czuk, G. Gu owski e al. Eu opean Jou nal o Combina o ics 102 (2022) 103505 Clea ly, Msa is ies condi ions (i)–(iii). Also, as in he p e ious case, he spli ing M=SN′is unique. Indeed, assume ha M=AB is any decomposi ion o Min o he p oduc o monomials om P′and Q, espec i ely. To ge in Bwe ha e o use he i s ac o o Q, since o he wise we ha e yin M. This al eady implies ha B=N′and A=S. Hence, cM(P)=cS(P′)·cN′(Q)= 0, so, Mis non- anishing in P. Subcase 3. The e is no special monomial. Finally, assume ha he e is no special monomial in P′. Howe e , by induc i e assump ion, he e is s ill a nice non- anishing monomial M′in he g aph polynomial P′=DG′−e. This monomial can be w i en now as M′=Yx 1 1x 2 2. . . x k k , whe e ⩽2, i⩽2, o all i=1,2,...,k, and Yis a monomial consis ing o he es o he a iables. As in Subcase 1, we ha e P=P′Q, whe e Q=(a +by)(c +d )(a1 +b1x1)(a2 +b2x2). . . (ak +bkxk). In he expansion o Qwe ge he monomial N= 2x1. . . xk, wi h cN(Q)=acb1···bk= 0. Hence, in he expansion o he p oduc P′Qwe ge he monomial M=M′N, which can be w i en as M=Yx 1+1 1x 2+1 2. . . x k+1 k 2. Clea ly Msa is ies condi ions (i)–(iii). We claim ha he e is only one way o exp essing Mas a p oduc o wo monomials, M=AB, wi h A om P′and B om Q. Indeed, o ge 2in Bwe ha e o choose a iable exac ly wice om he ac o s o Q. The i s choice mus be om he i s ac o , o he wise yappea s in M. The second choice mus be om he second ac o , since o he wise he a iable appea s in B, while some xiis missing. Then, in o de o ge M=AB, we would ha e o ha e −1and x i+1 iin he monomial A. Bu hen Ais a special monomial in P′, con a y o ou assump ion. Hence, we mus ha e B=Nand A=M′. Thus cM(P)=cM′(P′)·cN(Q)= 0, which demons a es ha Mis non- anishing in P. The p oo is comple e. □ In [8] G y czuk and Zhu p o ed ha e e y plana g aph Gcon ains a ma ching Ssuch ha AF(PG−S)⩽3. The p oo is simila o he abo e and can be easily modi ied o gi e he ollowing esul . Theo em 6. E e y plana g aph G con ains a ma ching S such ha AF(DG−S)⩽3, o an a bi a y ield F. Thus, G −S is F-4-choosable, and in pa icula , Z2×Z2-colo able. 2.5. K5-mino - ee g aphs To ex end he abo e esul s o g aphs wi hou a K5-mino we will use he well-known cha ac- e iza ion heo em o Wagne [18]. A simila app oach was aken by Abe, Kim, and Ozeki [1] in an ex ension o he esul o Zhu [21] o g aphs wi h no K5-mino . Recall ha a k-clique-sum o wo g aphs is a new g aph ob ained by gluing he wo g aphs along a clique o size kin each o hem, and possibly dele ing some edges o he clique. Recall also ha he Wagne g aph V8is he g aph ob ained om he cycle C8by adding ou edges joining an ipodal pai s o e ices. 6 B. Bosek, J. G y czuk, G. Gu owski e al. Eu opean Jou nal o Combina o ics 102 (2022) 103505 Theo em 7 (Wagne , [18]).E e y edge-maximal g aph wi hou a K5-mino can be buil ecu si ely om plana iangula ions and he g aph V8by clique-sums wi h cliques on a mos 3 e ices. We need he ollowing esul . Theo em 8. Le G be a plane iangula ion and le T be any iangle in G. Then he deco a ed g aph polynomial DG−E(T)o e an a bi a y ield Fcon ains a non- anishing monomial N such ha degu(N)=0, o e e y e ex u ∈V(T), and degw(N)⩽4, o all o he e ices. P oo . Le V(T)= {x,y, }and deno e e=xy. Suppose i s ha Tis a acial iangle. We may assume ha Tis he ou e ace o G.ByTheo em 5 we know ha he e is a non- anishing monomial Min DG−esuch ha degx(M)=degy(M)=0, deg (M)⩽2, and degw(M)⩽4, o all o he a iables. In o de o o m his monomial we ha e o pick exac ly wice; once om each ac o , (ax +b ) and (cy +d ), since we can choose nei he x, no y. Thus, when we dele e he co esponding wo edges x and y om he g aph G−e, we mus ha e a non- anishing monomial N=M/ 2in he polynomial DG−E(T). I Tis no a acial iangle, hen we may spli he iangula ion Gin o wo sub- iangula ions, G1 and G2, lying inside and ou side he iangle T, espec i ely. Then we may apply he same a gumen o each sub- iangula ion sepa a ely o ge he desi ed monomials N1and N2in polynomials DG1−E(T) and DG2−E(T), espec i ely. Clea ly, we ha e DG−E(T)=DG1−E(T)DG2−E(T), and i is easy o see ha N=N1N2is a non- anishing monomial in DG−E(T)sa is ying he asse ion o he heo em. □ Now we may gi e he p oo o he a o emen ioned ex ension o Theo em 4. Theo em 9. Le G be a g aph wi hou a K5-mino and le DGbe i s deco a ed g aph polynomial o e an a bi a y ield F. Then AF(DG)⩽4. P oo . Le Gbe an edge-maximal K5-mino - ee g aph. We p oceed by induc ion on he numbe o e ms in a clique-sum gi ing G. So, suppose ha Gis k-clique-sum, k⩽3, o wo g aphs Hand F, whe e His a clique-sum wi h a smalle numbe o e ms, while Fis a plane iangula ion o F=V8. Assume by induc ion ha AF(DH)⩽4, and le Mbe he monomial wi nessing his inequali y wi h coe icien cM(DH)= 0. In he iangula ion case, le {x,y,z}be he h ee e ices o he common iangle Tin Hand F. Le Nbe a monomial in DF−E(T)gua an eed by Theo em 8 wi h coe icien cN(DF−E(T))= 0. We claim ha he monomial MN occu s in he polynomial DGwi h coe icien cMN (DG)=cM(DH)·cN(DF−E(T)). Indeed, we ha e an ob ious equali y DG=DHDF−E(T)and he only common a iables o he wo polynomial ac o s a e x,y,z, none o which appea s in he monomial N. I F=V8, hen he easoning is simila . No ice ha V8is iangle- ee, so he clique-sum can be made on one e ex o one edge. Suppose i is he la e si ua ion ( he o me is e en easie ). Le x,ybe he wo common e ices o Hand F. I is enough o no ice ha o e e y edge e=xy o V8 he e is an acyclic o ien a ion o V8−ewi h in-deg ees o bo h e ices xand yequal o 0. The monomial Jco esponding o his o ien a ion has a non-ze o coe icien , he a iables xand ydo no occu in J, while o he a iables ha e deg ees a mos 3. Thus, as be o e we ha e cMJ (DG)=cM(DH)·cJ(DF−e)= 0. This comple es he p oo . □ By Theo ems 9 and 3we ge immedia ely he ollowing esul s, whose special case ex ends Z5-colo abili y o plana g aphs. Co olla y 2. Le Fbe an a bi a y ield wi h a leas 5elemen s. Then e e y g aph G wi hou a K5-mino is F-5-choosable. 7 B. Bosek, J. G y czuk, G. Gu owski e al. Eu opean Jou nal o Combina o ics 102 (2022) 103505 2.6. Ex ending o cyclic g oup choosabili y The polynomial me hod is ied o an ambien ield. One way o ex ending he po en ial esul s o cyclic g oups is o use cyclic subg oups o mul iplica i e g oups o ields wi h app op ia e o de and o exp ess he condi ions on he colo ing using mul iplica ion ins ead o addi ion. By his ick we ge he ollowing esul . Theo em 10. Le Γbe an a bi a y cyclic g oup o o de a leas 5. Then e e y K5-mino ee g aph G is Γ-5-choosable. P oo . Le Γbe a (mul iplica i e) cyclic g oup o o de m⩾5. Le pbe a p ime numbe such ha gcd(m,p)=1. Conside he ield F=Fpφ(m). I s mul iplica i e g oup F∗is he cyclic g oup o o de pφ(m)−1. Since mdi ides pφ(m)−1 (by Eule ’s heo em), Γis a subg oup o F∗. Le ℓbe a labeling o he edges o a g aph Gby he elemen s o Γ. Deno e by ℓij =ℓ(xixj) he label o an edge xixjin G. Fo any ixed o ien a ion  Go G, le dibe he in-deg ee o he e ex xi. Conside now he ollowing unc ion G(x1,x2,...,xn)=∏ (xi,xj)∈E( G) (xix−1 j−ℓij)=1 ∏n i=1xdi i ∏ (xi,xj)∈E( G) (xi−ℓijxj). By Theo em 9, he polynomial PG(x1,x2,...,xn)=∏ (xi,xj)∈E( G) (xi−ℓijxj) has a non anishing monomial o deg ee a mos ou . I ollows ha , o e e y collec ion o se s A1,A2,...,An⊆Γ⊆F∗, each wi h ca dinali y a leas i e, he e is a poin (a1,a2,...,an) in A1×A2×···×Anwhe e PGis no anishing, which implies ha G(a1,a2,...,an)= 0. I ollows ha (a1,a2,...,an) is a Γ-colo ing o G o he labeling ℓ.□ 2.7. The numbe o colo ings In his sec ion we p o e he second pa o Theo em 1. Ou main ool is he ollowing gene al esul o Alon and Fü edi [3]. Theo em 11 (Alon and Fü edi, [3]).Le Fbe an a bi a y ield, le A1,A2,...,Anbe any non-emp y subse s o F, and le B =A1×A2× ··· × An. Suppose ha P(x1,x2,...,xn)is a polynomial o e F ha does no anish on all o B. Then, he numbe o poin s in B o which P has a non-ze o alue is a leas min∏n i=1qi, whe e he minimum is aken o e all in ege s qisuch ha 1⩽qi⩽|Ai|and ∑n i=1qi⩾∑n i=1|Ai|−degP. Fo a con enien use o his esul , and o he sake o comple eness, we will p o e a sligh ly weake s a emen by an a gumen esembling a beau i ul p oo o Combina o ial Nulls ellensa z, due o Michałek [13]. A simila app oach was aken by Bishnoi, Cla k, Po ukuchi, and Schmi [4] o ge some gene aliza ion o he Alon-Fü edi heo em. We need a simple echnical lemma. Lemma 1. Le a1,a2,...,anbe posi i e in ege s, wi h maxai= ⩾2and ∑n i=1ai=S. Then A= n ∏ i=1 ai⩾ S−n −1.(2.5) P oo . The p oo is by induc ion on n. Fo n=1 we ha e A=a1= and S=a1= , hence we ge equali y in (2.5). Fo n⩾2, le ai0=min ai=m. Then, by he induc i e assump ion, we ha e A ai0=A m⩾ (S−m)−(n−1) −1. 8 B. Bosek, J. G y czuk, G. Gu owski e al. Eu opean Jou nal o Combina o ics 102 (2022) 103505 Obse e ha o e e y x∈ [1, ]we ha e x⩾ x−1 −1.(2.6) Indeed, i is no ha d o check ha he unc ion (x)= (x−1)/( −1) is con ex, wi h (1) =1 and ( )= . Hence, aking x=m, we may w i e A⩾m· (S−m)−(n−1) −1⩾ m−1 −1· (S−m)−(n−1) −1= S−n −1, as asse ed. □ Theo em 12. Le Fbe an a bi a y ield, and le A1,A2,...,Anbe any non-emp y subse s o F, wi h S=∑n i=1|Ai|and =max|Ai|. Le B =A1×A2×··· × Anand suppose ha P(x1,x2,...,xn)is a polynomial o e Fo deg ee deg P=d, ha does no anish on all o B. Then, he numbe o poin s in B o which P has a non-ze o alue is a leas S−n−d −1, p o ided ha S ⩾n+d and ⩾2. P oo . The p oo is by induc ion on dand n. I d=0, hen Pequals some non-ze o cons an c∈F, and he e o e all poin s o Ba e non- anishing o P. The e a e exac ly ∏n i=1|Ai|o hem, so, he asse ion ollows om Lemma 1 by pu ing ai= |Ai|. Fo n=1 and a bi a y d⩾1, we know ha he numbe o oo s o a polynomial Pis a mos d. Hence, he numbe o elemen s o A1 o which Pis non-ze o is a leas −d. So, by he assump ion ha ⩾d+1 and he inequali y (2.6), we ha e −d⩾ −1−d −1= S−1−d −1, as S= in his case. Assume now ha d⩾1 and n⩾2. Le |A1| = j, and assume, wi hou loss o gene ali y, ha he e is ano he se Ai, wi h |Ai| = . Le b∈A1be any elemen , and le us di ide he polynomial P by (x1−b): P=(x1−b)Qb+Rb. Obse e ha degQb=degP−1=d−1, degRb⩽d, and ha he polynomial Rbdoes no con ain he a iable x1. Suppose i s ha he polynomial Rb anishes a all poin s o he g id A2×···×An. This implies ha j⩾2, since o he wise, he polynomial Pwould anish o e he whole g id B, con a y o he assump ion. Fu he mo e, each non- anishing poin o Pin Bis a he same ime a non- anishing poin o Qbin he g id (A1−b)×A2×···×An, and ice e sa. Thus, by he induc i e assump ion we ge ha Phas a leas (S−1)−n−(d−1) −1= S−n−d −1 non- anishing poin s in B. Finally, suppose ha o e e y b∈A1, he polynomial Rbhas some non- anishing poin s in he g id A2×···×An. Then each such poin can be ex ended o a non- anishing poin o Pby se ing x1=b. By he induc i e assump ion on n, he numbe o such poin s o each Rbis a leas (S−j)−(n−1)−d −1. Hence, he o al numbe o non- anishing poin s o Pin he g id Bis a leas j· (S−j)−(n−1)−d −1⩾ j−1 −1· (S−j)−(n−1)−d −1= S−n−d −1, by he inequali y (2.6). The p oo is comple e. □ The abo e esul and Theo em 9 easily imply he ollowing co olla y. 9