Normal edge‐colorings of cubic graphs
Normal edge‐colorings of cubic graphs
复制标题
DOI：
10.1002/jgt.22507
复制
发表时间：
2018-04
影响因子：
0.9
通讯作者：
G. Mazzuoccolo;V. Mkrtchyan
中科院分区：
文献类型：
--
作者：
G. Mazzuoccolo;V. Mkrtchyan
三次图的正常k-边染色是具有k个颜色的正常边染色，具有附加性质，即当查看分配给任何边e及其相邻的四条边的颜色集合时，我们恰好有五种不同的颜色或恰好有三种不同的颜色。我们用χ N ′（G）表示最小的k，使得G允许正常的k-边染色。正规k边着色是由Jaeger引入来研究他著名的Petersen着色猜想的。更准确地说，证明对于每个无桥立方图χ N ′（G）≤ 5等价于证明彼得森着色猜想，然后它意味着圈双覆盖猜想和Berge-Fulkerson猜想。考虑到所有简单三次图（不一定是无桥的）的较大类，自然会出现一些有趣的问题。例如，存在非无桥的简单三次图，且χ N ′（G）= 7。与此相反，已知χ N ′（G）的最佳广义上界为9。在这里，我们改进了它，证明了对任意简单三次图G，χ N ′（G）≤ 7是最佳可能的.我们通过证明4-边连通图中存在特定无处为零的Z 2 2-流来得到这个结果。
A normal k ‐edge‐coloring of a cubic graph is a proper edge‐coloring with k colors having the additional property that when looking at the set of colors assigned to any edge e and the four edges adjacent to it, we have either exactly five distinct colors or exactly three distinct colors. We denote by χ N ′ ( G ) the smallest k , for which G admits a normal k ‐edge‐coloring. Normal k ‐edge‐colorings were introduced by Jaeger to study his well‐known Petersen Coloring Conjecture. More precisely, it is known that proving χ N ′ ( G ) ≤ 5 for every bridgeless cubic graph is equivalent to proving the Petersen Coloring Conjecture and then it implies, among others, Cycle Double Cover Conjecture and Berge‐Fulkerson Conjecture. Considering the larger class of all simple cubic graphs (not necessarily bridgeless), some interesting questions naturally arise. For instance, there exist simple cubic graphs, not bridgeless, with χ N ′ ( G ) = 7 . In contrast, the known best general upper bound for χ N ′ ( G ) was 9 . Here, we improve it by proving that χ N ′ ( G ) ≤ 7 for any simple cubic graph G , which is best possible. We obtain this result by proving the existence of specific nowhere zero Z 2 2 ‐flows in 4 ‐edge‐connected graphs.