关于图的模边着色-计算机科学-算法.pdfVIP

关于图的模边着色

12343

GaétanBerthe,MartheBonamy,FábioBotler,GaiaCarenini,LucasColucci,

563

ArthurDumas,FatemehGhasemi,andPedroMarianoVianaNeto

1CNRS,LIRMM,UniversitédeMontpellier,Montpellier,France.

2CNRS,LaBRI,UniversitédeBordeaux,Bordeaux,France.

3InstitutodeMatemáticaeEstatística,UniversidadedeSãoPaulo,Brazil.

本4DPMMS,UniversityofCambridge,Cambridge,UnitedKingdom.

译5UniversitédeLyon,CNRS,INSALyon,UCBL,CentraleLyon,UniversitéLyon2,

中LIRIS,UMR5205,Villeurbanne,France.

16UniversitéParis-EstCréteil,LACL,Creteil,France.

v

4

52025年7月9日

2

4

0

.

7摘要

0

给定一个图和一个整数，令表示所需最少的颜色数量，用于对的边进行着

5

2色，使得在每种颜色类中，由那种颜色的边诱导出的子图的所有非零度数都与模同余。1992

:

v年，Pyber证明了对于每个图都有成立，并提出了一个问题，即是否可以仅根据

i

x来限定每一个的。这个问题在1997年由Scott回答，他证明了log，

r

并进一步询问了是否。最近，Botler、Colucci和Kohayakawa（2023）肯定地回

a

答了Scott的问题，证明了，并猜测乘法常数可以减少到。2024年，Nweit

和Yang向这一后一猜想迈进了一步，将界限改进为。在这篇论文中，我们

将乘法常数进一步改进到了。更具体地说，我们证明存在一个函数，使得如果是奇

数，则，如果是偶数，则。通过这样做，我们证明了对

于每个退化图，成立，这在我们的证明中起着核心作用。

关键词：模-色指数，退化图，