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