几类IC-平面图的退化性 Degeneracy of Some Classes of IC-Planar Graphs

doi:10.12677/AAM.2021.1010356

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

AdvancesinAppliedMathematicsA^êÆ?Ð,2021,10(10),3390-3398

PublishedOnlineOctober2021inHans.http://www.hanspub.org/journal/aam

https://doi.org/10.12677/aam.2021.1010356

AaIC-²¡ãòz5

XXXõõõhhh

úô“‰ŒÆ§êÆ†OŽÅ‰ÆÆ§úô7u

ÂvFÏµ2021c918F¶¹^FÏµ2021c1014F¶uÙFÏµ2021c1021F

Á‡

eãGz˜‡fãHÑkδ(H)≤k,K¡G´k-òz.ŠâØ¹k-(k∈{3,5,6})²¡ã

´3-òz,©y²Ø¹k-IC-²¡ã´4-òz.©„?˜Úy²3-†4-Ø

ƒ,3-†5-Øƒ½4-†4-ØƒIC-²¡ã•´4-òz.Óž,©‰ÑØ

¹k-(k∈{3,4,5,6})…4-KIC-²¡ã~f"

'…c

IC-²¡ã§òz5§=£

DegeneracyofSomeClassesofIC-Planar

Graphs

HonghuiTian

DepartmentofMathematics,ZhejiangNormalUniversity,JinhuaZhejiang

Received:Sep.18

,2021;accepted:Oct.14

,2021;published:Oct.21

,2021

Abstract

IfeverysubgraphH ofgraphGhasδ(H)≤k,thenGisk-degenerate.Aplanar

©ÙÚ^:Xõh.AaIC-²¡ãòz5[J].A^êÆ?Ð,2021,10(10):3390-3398.

DOI:10.12677/aam.2021.1010356

Xõh

graphwithoutk-cycles(k∈{3,5,6})is3-degenerate,thispaperprovesthatanIC-

planargraphwithoutk-cyclesis4-degenerate.Thispaperisfurtherprovedthatthe

IC-planargraphwith3-cycl enotadjacentto4-cycle,3-cyclenotadjacentto5-cycle

or4-cyclenotadjacentto4-cycleisalso4-degenerate.Andwegiveanexampleof

4-regularIC-planargraphswithoutk-cycles(k∈{3,4,5,6}).

Keywords

IC-PlanarGraph,Degeneracy,Discharging

2021byauthor(s)andHansPublishersInc.

This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).

http://creativecommons.org/licenses/by/4.0/

1.Úó

©¤?ØãÑ´k•{üÃ•ã.©¥™\`²âŠ„©[1].V(G),E(G)©OL«

ãGº:8 Ú>8.²¡ã´ã3²¡þ˜«i\,¦?¿ü^>=3à:?ƒ.eG´²

¡ã,·‚^F(G)5L«ãG¡8.XJãGŒ±i\²¡þ,¦z^>•õ˜g,K

¡Ù•1-²¡ã,T²¡i\¡•1-²¡i\.1-²¡ã´Ringel[2]u1965cïÄ²¡ã:-¡/

ÚžJÑ.eãG´1-²¡ã…•3˜«²¡i\,¦¹:>|¤8Ü´ãG˜‡

š(=?¿ü^ >o‡à:ÑØ-Ü),K¡ãG´IC-²¡ã,T²¡i\¡•IC-²¡i

\.IC-²¡ã´Alberson[3]32008cJÑ5,¿ßŽz‡IC-²¡ãÑ´5-Œ/.dßŽ5

Kral†Stacho[4]y²¤á.eãGIC-²¡i\÷vÙ:‡ê´¤kIC-²¡ i\¥•,

K¡dIC-²¡i\••`IC-²¡i\.

G´IC-²¡ã…´•`IC-²¡i\.-C(G)´G¥¤k:|¤8Ü,E

(G)´G¥Ø

¹:>|¤8Ü.UXe•ª½ÂG'é²¡ãG

:V(G

)=V(G)∪C(G),E(G

(G) ∪{xz,yz|xy∈E(G) \E

(G),…z´¹3>xyþ:}.KG

´²¡ã,…é?¿z∈

C(G),kd

(z)=4.¡C(G)¥:•b:,V(G)¥:•ý:.dIC-²¡ã½Â•?¿ü‡

b:3G

¥Øƒ,…z˜‡ý:–õ†˜‡b:ƒ.eG

¥¡f–†˜‡b:'é,K

¡f•b¡;Ø†b:'é¡¡•ý¡.

-v∈V(G),¡:v¤k:|¤8Ü•:v•,PŠN

(v).¡d

(v)= |N

(v)|•v

Ýê.δ(G)=min{d

(v)|v∈V(G)}Ú∆(G)=max{d

(v)|v∈V(G)}©O¡ŠG•ÝÚ•

ŒÝ.G´IC-²¡ã,f∈F(G

).¡†¡fƒ'é>ê•¡fÝê(z^•>OŽüg),P

•d

(f).v∈V(G),XJd

(v)=k,≥k,½≤k,K¡v•k-:,k

-:½k

−

-:.aq/,Œ

DOI:10.12677/aam.2021.10103563391A^êÆ?Ð

Xõh

±½Âk-¡,k

-¡½k

−

-¡.-f∈F(G

),ef>.:U^ž•••g•v

,···,v

KŒPŠf=[v

···v

].^d

(f)Úd

(f)©OL«†f'ék-:†k

-:‡ê;^f

(v),

(v)Úf

−

(v)©OL«G

¥†v'éi-¡,i

-¡Úi

−

-¡‡ê,^α(v)5L«†v'éb3-

¡‡ê.

eãGz˜‡fãHÑkδ(H)≤k,K¡ãG´k-òz.ŠâëÏ²¡ãEulerúªÚ

ºÃ½n´?¿˜‡²¡ãÑ´5-òz;?¿˜‡Ø¹3-²¡ãÑ´3-òz.2002c,

WangÚLih[5]ü Æöy²Ø¹5-²¡ã´3-òz.Óc,Fijvaz[6]y²Ø¹6-

²¡ã´3-òz.©|^þã(J,y²Ø¹k-(k∈{3,5,6})IC-²¡ãÑ´4-òz.

¿‰ÑØ¹k-(k∈{3,4,5,6})…4-KIC-²¡ã.Óž,©?˜Úy² 3-Ú4-Øƒ,

3-Ú5-Øƒ½4-Ú4-ØƒIC-²¡ã•´4-òz.

2.3-Ø†4-ƒIC-²¡ãòz5

½½½nnn2.1.Ø¹k-(k∈{3,5,6})IC-²¡ãÑ´4-òz.

y².G´IC-²¡ã…®IC-²¡i\,E

(G)´G¥Ø¹:>|¤8Ü,E

(G)´G¥¹

:>|¤8Ü.KdIC-²¡ã½Â•,dE

(G)¥>ÑfãG

´²¡ã,dE

(G)¥

>Ñfã´1-Kã.dK¿•G

´Ø¹k-(k∈{3,5,6})²¡ã.G

´3-òz.l

G´4-òz.

½½½nnn2.2.3-Ø†4-ƒIC-²¡ã´4-òz.

y².G´½n2.2:ê•4‡~ã.w,G´ëÏ,G´•`IC-²¡i\.w,

äó2.1¤á.

äó2.1δ(G) ≥5.

Ï•G´3-Ø†4-ƒIC-²¡ã,¤±äó2.2¤á.

äó2.2ý3-¡†ý3-¡Øƒ.

äó2.3z˜‡5

-:v–'é2‡4

-¡.

y².dv–õ†˜‡b:•α(v)≤2.α(v)=0,däó2.2•f

(v)≤b

(v )

c.v'é

4

-¡‡ê≥d

(v)−b

(v )

c≥3.α(v) =1ž,Ø”†v'éb3-¡•f

= [vv

]…v

•b

:.K†v'é…±vv

•>.¡7•4

-¡.däó2.2•f

(v)≤d

(v )−2

e+ 1=d

(v )

e.v'

é4

-¡‡ê≥d

(v) −d

(v )

e≥2.α(v)=2ž,dv–õƒ˜‡b:•,†v'éü‡

b3-¡7•f

=[vv

]Úf

=[vv

]…v

•b:.dž,†v'é…±vv

(½vv

)•>.>ØÓ

(½f

)¡•4

-¡.v–'éü‡4

-¡.nþ,z˜‡5

-:–'é2‡4

-¡.

äó2.4z˜‡b:–õ'é2‡b3-¡.

y².‡y{.v´b:,…Ù3G

¥4‡:•v

…3²¡þ•^ž••ü.

∈E(G)…v

∈E(G).bf

=[vv

],f

=[vv

]9f

=[vv

]´3-¡.KG¥¹ƒ

3-v

Ú4-v

,gñ.¤±,z˜‡b:–õ'é2‡b3-¡.

e¡·‚^=£•{¤½n2.2y².év∈V(G

),-ch(v)=d

(v) −6;éf∈

DOI:10.12677/aam.2021.10103563392A^êÆ?Ð

Xõh

F(G

),-ch(f) = 2d

(f)−6.(Üî.úª|V(G

)|−|E(G

)|+|F(G

)|= 2ÚºÃ½n,Œ±

e¡ðªµ

x∈V(G

)∪F(G

)

ch(x) =

x∈V(G

)

(v)−6)+

x∈F(G

)

(2d

(f)−6) = −12

e¡½Â·=£5K,…3=£L§¥,oÚ±ØC.-ch

(x)´x∈V(G

) ∪

F(G

)3²L=£ƒ•ª.eUy²é¤kx∈V(G

)∪F(G

),kch

(x)≥0.ù

Ò†þ¡ðª/¤gñ,l¤½n2.2y².

·‚½ÂXe=£5Kµ

R1µz˜‡4

-¡=

(f)−6

(f)

‰'éz˜‡:.

²LR1ƒ,z˜‡5

-:v•β(v).

R2µz˜‡5

-:òmax{0,β(v)}=‰†§ƒb:.

dR1Œäó2.5¤á.

äó2.51)z‡4-¡=

‰¤'é:.

2)z‡4-¡=

‰¤'é:.

3)z‡6

-¡=1‰¤'é:.

e¡yéu∀x∈V(G

)∪F(G

),Ñkch

(x) ≥0.

f∈F(G

).ed

(f)=3,Kch

(f)=ch(f) = 2d

(v)−6 =0.ed

(f)≥4,KdR1•,

(f) = ch(f)−

(f)−6

(f)

×d

(f) = 0.

v∈V(G

).ed

(v)≥5,Kd=£5K•,•‡yβ(v)≥0.däó2.3,ä

ó2.5ÚR1Œ±β(v)≥d

(v) −6+ 2×

≥0.e¡d

(v)=4.däó2.1•v•b:.

v3G

¥4‡:•v

…3²¡þ•^ž••ü.-f

´±vv

,vv

i+1

•>.¡,

i= 1,2,3,4…v

= v

.däó2.1•d

) ≥5,i= 1,2,3,4.dIC-²¡ã½Â•,v

¥

:(Øv)•ý:.

œ¹1µvØ†b3-¡'é

däó2.5•,ch

(v) ≥d

(v)−6+

×4 = 0.

œ¹2µv†˜‡b3-¡'é

Ø”d

)=3,=f

=[vv

].K†v

Úv

ƒ:Ñ´ý:.däó2.2•,f

)≤

)−2

e.v

–†d

) −f

)≥d

) −d

)−2

e≥3‡4

-¡.lβ(v

)≥

)−6+

×3 =

.dR2•v

–=

‰v.däó2.5•, ch

(v) ≥d

(v)−6+

×3+

= 0.

œ¹3µv†ü‡b3-¡'é

f

=[vv

]…f

=[vv

].Kd3-Ø†4-…v

:•ý:•,±v

•

>.>…ØÓuf

¡•5

-¡.Ón,±v

•>.>…ØÓuf

¡•5

-¡.däó2.5•,

DOI:10.12677/aam.2021.10103563393A^êÆ?Ð

Xõh

β(v

)≥d

) −6 +

×2=

.dR2•v

–=

‰v.däó2.2•f

)≤d

)−2

¤±v

–†d

) −f

)≥d

) −d

)−2

e≥3‡4

-¡.ldäó2.5•β(v

)≥

)−6+

×3 =

,…dR2•v

–=

‰v.däó2.5•ch

(v) ≥d

(v)−6+

×2 =

f

=[vv

]…f

=[vv

].Kv

†4-v

'é,i=1,2,3,4.d3-†4-Ø•,

±v

•>.>…ØÓuf

¡•4

−¡.Ón,±v

•>.>…ØÓuf

¡•4

−¡.dä

ó2.2•,f

) ≤1+d

)−3

e= d

)−1

e,i= 1,2,3,4.lv

–†d

)−d

)−1

e≥

3‡4

−¡'é.ldäó2.5•,β(v

)≥d

)−6+

×3=

.dR2•,v

(i= 1,2,3,4)–

=

‰v.ch

(v) ≥d

(v)−6+

×4 = 0.

d½n2.2Œ±eíØ.

íííØØØ2.3.Ø¹4-IC-²¡ã´4-òz.

d½n2.1ÚíØ2.3Œ±eíØ.

íííØØØ2.4.Ø¹k-(k∈{3,4,5,6})IC-²¡ã´4-òz.

e¡·‚‰Ñ~f`²íØ2.4(Ø´;.ã1´Ø¹3-†5-4-KIC-²¡ã.

›¡Nã‚ã´Ø¹4-4-KIC-²¡ã.K

´Ø¹6-4-KIC-²¡ã.

Figure1.4-regularBipartiteIC-planargraph

ã1.4-KÜIC-²¡ã

3.3-Ø†5-ƒIC-²¡ãòz5

½½½nnn3.1.3-Ø†5-ƒIC-²¡ã´4-òz.

y².G´½n3.1:ê4‡~ã.w,G´ëÏ,G´•`IC-²¡i\.w,ä

ó3.1¤á.

äó3.1δ(G) ≥5.

DOI:10.12677/aam.2021.10103563394A^êÆ?Ð

Xõh

v∈V(G

)´˜‡ý:.-v

,···,v

´v3G

…¥:…3²¡þ•^ž••ü.

-f

´±vv

,vv

i+1

•>.>¡,Ù¥i=1,2,···,d…v

d+1

.-f

i+1

i+2

•ƒUn‡¡.

d3-Ø†5-•f

i+1

i+2

¥7k˜‡4

-¡½b3-¡.äó3.2¤á.

äó3.2z˜‡ý:vØ†n‡ƒUý3-¡'é.

äó3.3z‡5

-:v–'é2‡4

-¡.

y².dv–õ†˜‡b:•α(v)≤2.α(v)=0,däó3.2•f

(v)≤b

(v )

c.v–'

éd

(v)−f

(v)≥d

(v)−b

(v )

c≥2‡4

-¡.α(v)=1ž,Ø”†v'éb3-¡•f

[vv

]…v

•b:.K±vv

•>.>…ØÓuf¡•4

-¡.däó3.2•f

(v)≤d

2(d

(v )−1)

v–'éd

(v)−f

(v)≥d

(v)−b

2(d

(v )−1)

c≥2‡4

-¡.α(v)= 2ž,dv–õƒ˜‡

b:•,†v'éü‡b3-¡7•f

=[vv

]Úf

=[vv

],…v

•b:.-f

©O±vv

•>

.>…ØÓuf

¡Ú±vv

•>.>…ØÓuf

¡.ed

) ≥4…d

) ≥4,Kv–'é

ü‡4

-¡.ed

)=3,=f

=[vv

],Kd3-Ø†5-•±vv

•>.>…ØÓuf

¡

•4

-¡.v–'éü‡4

-¡.nþ,z˜‡5

-:–'é2‡4

-¡.

e¡·‚^=£5K¤½n3.1y².

·‚æ^†½n2.2ƒÓÐ©¼ê9=£5K.e5,·‚I‡y²é¤kx∈

V(G

)∪F(G

),kch

(x) ≥0.íÑ†½n2.2˜gñ,l¤é½n3.1y².

dR1Œäó3.4¤á.

äó3.41)z‡4-¡=

‰¤'é:.

2)z‡4-¡=

‰¤'é:.

3)z‡6

-¡=1‰¤'é:.

e¡yéu∀x∈V(G

)∪F(G

),Ñkch

(x) ≥0.

f∈F(G

).ed

(f)=3,Kch

(f)=ch(f) = 2d

(v)−6 =0.ed

(f)≥4,KdR1•,

(f) = ch(f)−

(f)−6

(f)

×d

(f) = 0.

v∈V(G

).ed

(v)≥5,Kd=£5K•,•‡yβ(v)≥0.ÏLäó3.3,

äó3.4ÚR1Œ•β(v)≥d

(v)−6+2×

≥0.ed

(v)=4.däó3.1•v•b:.

v3G

¥4‡:•v

…3²¡þ•^ž••ü.-f

´±vv

,vv

i+1

•>.

¡,i=1,2,3,4…v

.däó3.1•d

)≥5,i=1,2,3,4.dIC-²¡ã½Â•,v

:(Øv)•ý:,i= 1,2,3,4.

œ¹1µv†o‡b3-¡'é

=[vv

],f

=[vv

],f

=[vv

]…f

=[vv

].dv

•†˜‡b:ƒ•v

ØvÙ{:•ý:.-f

´±v

•>.>…ØÓuf

¡,f

´±v

•>.>…ØÓ

¡.-f

=[v

···x

].ed

)=3,=f

=[v

],KG¥¹ƒ3-v

Ú5-

v

,gñ.ed

) = 4,=f

= [v

],dIC-²¡ã½Â•x

†x

•ý:.dδ(G) ≥

5•x

/∈{v

},KG¥¹ƒ3-v

Ú5-v

,gñ.d

)≥

5.dé¡5,d

)≥5.ldäó3.4•,β(v)≥d

(v) −6+

×2=

.dR2•,v

–=

DOI:10.12677/aam.2021.10103563395A^êÆ?Ð

Xõh



‰v.dé¡5,v

ˆ–=

‰v.Ïd,ch

(v) ≥d

(v)−6+4×

œ¹2µv†n‡b3-¡'é.

Ø”f

=[vv

],f

=[vv

]†f

=[vv

].eyd

)≥6.¯¢þ,XJd

)=4,

= [vv

],Kdäó3.1•x/∈{v

},G¥¹ƒ3-v

Ú5-v

gñ.XJd

)=5,=f

=[vv

],@odäó3.1•x

/∈{v

},¤±G¥¹

ƒ3-v

Ú5-v

,gñ.¤±,d

)≥6.däó3.3Ú3.4•,β(v

)≥

) −6+

+ 1=

.dR2•,v

–=

‰v.Ón,v

–=

‰v.Ïd,ch

(v)≥

(v)−6+1+

= 0.

œ¹3µv†ü‡b3-¡'é.

kf

=[vv

]†f

=[vv

].eyd

)≥5.¯¢þ,XJd

)=4,=f

[vv

],Kdäó3.1•x/∈{v

},G¥¹ƒ3-v

Ú5-v

,gñ.

d

)≥5.dé¡5,d

)≥5.däó3.3Ú3.4•,β(v

)≥d

) −6 +

dR2•,v

–=

‰v.dé¡5,v

–=

‰v.Ïd,däó3.4•ch

(v)≥d

(v) −6+

2×

+2×

2f

=[vv

]Úf

=[vv

].ed

)≥5½d

)≥5,Ø”d

)≥5,Kdä

ó3.3Ú3.4•,β(v

)≥d

) −6 +

.dR2•,v

–=

‰v.Ón,v

–=



‰v.@odäó3.4•ch

(v)≥d

(v)−6+2×

+2×

.ed

) =d

) =4,

=[vv

]Úf

=[vv

].däó3.1•x,y/∈{v

}.-f

´±v

x•>.>…ØÓ

¡,…f

=[v

···z

].ed

)=3,KG¥¹ƒ3-v

Ú5-v

ñ.d

)≥4.aqŒ±y²±v

•>.>…ØÓuf

¡•4

-¡.däó3.4•,β(v

)≥

)−6+

×3 =

.dé¡5, kβ(v

) ≥

, i= 2,3,4.dR2•,v

(i= 1,2,3,4)–=

‰v.

Ïd,däó3.4•ch

(v) ≥d

(v)−6+2×

+4×

= 1.

œ¹4µv†˜‡b3-¡'é.

Ø”d

)=3,=f

=[vv

].däó3.2•,f

)≤d

2(d

)−2)

e.lv

–'

éd

) −f

)≥d

) −d

2(d

)−2)

e≥3‡4

-¡.däó3.4•,β(v

)≥d

) −6 +

×3 =

.dR2•,v

–=

‰v.Ïd,däó3.4•ch

(v) ≥d

(v)−6+3×

+×

= 0.

œ¹5µvØ†b3-¡'é

däó3.4•,ch

(v) ≥d

(v)−6+

×4 = 0.

4.4-Ø†4-ƒIC-²¡ãòz5

½½½nnn4.1.4-Ø†4-ƒIC-²¡ã´4-òz.

y².G´½n4.1:ê4‡~ã.w,G´ëÏ,G´•`IC-²¡i\.w,ä

ó4.1¤á.

äó4.1δ(G) ≥5.

v∈V(G

)´˜‡ý:.-v

,d¸ots,v

´v3G

…¥:…3²¡þ•^ž••

DOI:10.12677/aam.2021.10103563396A^êÆ?Ð

Xõh

ü.-f

´±vv

,vv

i+1

•>.>¡,Ù¥i=1,2,···,d…v

d+1

.d4-Ø†4-

•f

i+1

i+2

¥7k˜‡4

-¡½b3-¡.äó4.2¤á.

äó4.2z˜‡ý:vØ†n‡ƒUý3-¡'é.

aqäó3.3y²,Œäó4.3¤á.

äó4.3z‡5

-:v–'é2‡4

-¡.

äó4.4z˜‡b:–õ'é3‡b3-¡.

y².v´b:,…Ù3G

¥4‡:•v

¿…3²¡þ•^ž••ü.Kv

∈

E(G)…v

∈E(G).-f

´±vv

Úvv

i+1

•>.>¡,Ù¥i=1,2,3,4…v

.·‚b

f

=[vv

],f

=[vv

],f

=[vv

]…f

=[vv

].KG¥¹ƒ4-v

Ú4-

v

,gñ.¤±,z˜‡b:–õ'é3‡b3-¡.

e¡·‚^=£5K¤½n4y².

V(G

)∪F(G

),kch

(x) ≥0.líÑ†½n2.2˜gñ,l¤é½n4.1y².

dR1Œäó4.5¤á.

äó4.51)z‡4-¡=

‰¤'é:.

2)z‡4-¡=

‰¤'é:.

3)z‡6

-¡=1‰¤'é:.

e¡yéu∀x∈V(G

)∪F(G

),Ñkch

(x) ≥0.

f∈F(G

).ed

(f)=3,Kch

(f)=ch(f) = 2d

(v)−6 =0.ed

(f)≥4,KdR1•,

(f) = ch(f)−

(f)−6

(f)

×d

(f) = 0.

v∈V(G

).ed

(v)≥5,d=£5K•,Iyβ(v)≥0.däó4.3,äó4.4ÚR1•β(v)≥

(v)−6+2×

≥0.ed

(v) = 4.däó4.1•v•b:.-v3G

¥4‡:•v

…

3²¡þ•^ž••ü.Kv

∈E(G)…v

∈E(G).-f

´±vv

,vv

i+1

•>.¡,

i=1,2,3,4…v

.däó4.4•,v–õ'é3‡b3-¡.däó4.1•d

)≥5,i=1,2,3,4.

dIC-²¡ã½Â•,v

¥:(Øv)•ý:,i= 1,2,3,4.

œ¹1µv†n‡b3-¡'é.

Ø”f

=[vv

],f

=[vv

]†f

=[vv

].eyd

)≥5.¯¢þ,ed

)=4,

= [vv

],Kdäó4.1•x/∈{v

}.G¥¹ƒ4-v

Ú4-v

gñ.¤±d

)≥5.-f

´±v

•>.>…ØÓuf

¡.ed

)=3,=f

],däó4.1•y

/∈{v

}.G¥¹ƒ4-v

Ú4-v

ñ.ed

)=4,=f

=[v

],däó4.1•y

/∈{v

},y

´ý:,G¥

¹ƒ4-v

Ú4-v

,gñ.d

)≥5,ldäó4.5•,β(v

)≥

)−6+

×2=

.dR2•,v

–=

‰v.dé¡5,v

–=

‰v.dä

ó4.5•ch

(v) ≥d

(v)−6+

+2×

= 0.

DOI:10.12677/aam.2021.10103563397A^êÆ?Ð

Xõh

œ¹2µv†ü‡b3-¡'é.

kf

= [vv

]…f

= [vv

].kyf

Úf

¥–k˜‡5

-¡.¯¢þ, ef

= [vv

]…f

[vv

],däó4.1•x6= y…x,y/∈{v

},džG¥¹ƒ4-v

Ú4-v

ñ.f

Úf

¥–k˜‡´5

-¡.däó4.2•,f

)≤d

2(d

)−2)

e.v

–†d

) −

) ≥d

)−d

2(d

)−2)

e≥3 ‡4

-¡.däó4.5•, β(v

) ≥d

)−6+

×2+

dR2•,v

–=

‰v.däó4.5•ch

(v) ≥d

(v)−6+

2f

=[vv

]Úf

=[vv

].eyd

)≥5…d

)≥5.¯¢þ,dé¡5Ø

”f

=[vv

].däó4.1•x6=y…x,y/∈{v

},G¥¹ƒ4-v

Ú4-

v

,gñ.d

) ≥5…d

) ≥5.däó4.5•,β(v

) ≥d

)−6+

,i=

1,2,3,4.dR2•,v

–=

‰v,i= 1,2,3,4.däó4.5•ch

(v) ≥d

(v)−6+4×

+2×

œ¹3µv†˜‡b3-¡'é.

Ø”d

) = 3,=f

= [vv

].däó4.2•, f

) ≤d

2(d

)−2)

e.v

–†d

)−

) ≥d

)−d

2(d

)−2)

e≥3‡4

-¡'é.däó4.5•,β(v

) ≥d

)−6+

×3 =

dR2•,v

–=

‰v.Ïd,däó4.5•ch

(v) ≥d

(v)−6+3×

= 0.

œ¹4µvØ†b3-¡'é

däó4.5•,ch

(v) ≥d

(v)−6+

×4 = 0.

ë•©z

[1]Bondy,J.A.andMurty,U.S.R.(1976)GraphTheorywithApplications.North-Holland,New

York.

[2]Ringel,G.(1965)EinSechsfarbenproblemaufderKugel.AbhandlungenausdemMathema-

tischenSeminarderUniversit¨atHamburg,29,107-117.(InGerman)

https://doi.org/10.1007/BF02996313

[3]Alberson, M. (2008)Chromatic Number, IndependentRatio, and CrossingNumber. ArsMath-

ematicaContemporanea,1,1-6.https://doi.org/10.26493/1855-3974.10.2d0

[4]Kral,D.andStacho,L.(2010)ColoringPlaneGraphswithIndependentCrossings.Journal

ofGraphTheory,64,184-205.https://doi.org/10.1002/jgt.20448

[5]Wang,W.andLih,K.W.(2002)ChoosabilityandEdgeChoosabilityPlanarGraphswithout

FiveCycles.AppliedMathematicsLetters,15,561-565.

https://doi.org/10.1016/S0893-9659(02)80007-6

[6]Fijavz,G.,Juvan,M.,Mohar,B.andSkrekovski,R.(2002)PlanarGraphswithoutCyclesof

SpeciﬁcLengths.EuropeanJournalofCombinatorics,23,377-388.

https://doi.org/10.1006/eujc.2002.0570

DOI:10.12677/aam.2021.10103563398A^êÆ?Ð