染色缺陷数较小的非平凡Snark图的部分规范6-边染色

Partial Normal 6-Edge-Coloring of Non-Trivial Snarks with Small Coloring Defect Number

摘要: 三正则图的边染色问题是图论领域的核心研究课题之一，无桥三正则图作为其中的重要图类，其边染色性质与Petersen着色猜想、Berge-Fulkerson猜想等经典图论猜想密切相关。根据Vizing定理，三正则图的边色数仅为3或4，非3边可染的无桥三正则图被称为snark图，这类图的规范边染色上界研究是该领域的难点。在三正则图的正常边着色中，若与边e的一个端点相关联的五条边所使用的颜色集合的基数为3或5，则称边e为规范边。三正则图的规范k-边着色，是指使用k种颜色对三正则图进行的边着色，且图中任意边均为规范边。我们用规范染色指数${{\chi }^{\prime }}_N\left(G\right)$ 表示使得图G存在规范k-边着色的最小正整数k。现有研究已证明无桥三正则图规范染色指数不超过7，且学者们提出了规范染色指数不超过6的猜想，同时得到了部分规范6-边染色下规范边的比例下界，但关于6-边着色下非规范边的精准上界、圈核结构与染色缺陷数对染色结果的影响仍缺乏系统研究。本文以无桥三正则图为研究对象，围绕其部分规范6-边着色问题展开深入探究，以核、1-因子等图论概念为基础，通过构造主染色并逐步延拓至整个图的方式，分情况讨论了不同圈核结构的无桥三正则图的6-边着色策略。研究了染色缺陷数小于等于5的非平凡snark图，并证明了存在规范6-边染色，使得最多只有一条非规范边。

Abstract: The edge-coloring problem of cubic graphs is one of the core research topics in graph theory. As an important class of graphs, bridgeless cubic graphs have edge-coloring properties closely related to classic graph theory conjectures such as the Petersen Coloring Conjecture and the Berge-Fulkerson Conjecture. According to Vizing’s Theorem, the edge chromatic number of a cubic graph is either 3 or 4. A bridgeless cubic graph that is not 3-edge-colorable is called a snark, and the research on the upper bound of the normal edge-coloring of such graphs is a difficult point in this field. In a proper edge-coloring of a cubic graph, an edge e is said to be normal if the cardinality of the color set used for the five edges incident to one endpoint of e is 3 or 5. A normal k-edge-coloring of a cubic graph refers to an edge-coloring of the cubic graph using k colors, where every edge in the graph is normal. We use the normal chromatic index ${{\chi }^{\prime }}_N\left(G\right)$ to denote the smallest positive integer k for which a normal k-edge-coloring of graph G exists. Existing studies have proven that the normal chromatic index of any bridgeless cubic graph is at most 7. Scholars have proposed the conjecture that the normal chromatic index is at most 6, and have obtained the lower bound of the proportion of normal edges under partial normal 6-edge-coloring. However, there is still a lack of systematic research on the precise upper bound of non-normal edges under 6-edge-coloring, and the influence of cycle core structures and coloring defect numbers on coloring results. Taking bridgeless cubic graphs as the research object, this paper conducts an in-depth study on the problem of their partial normal 6-edge-coloring. Based on graph theory concepts such as cores and 1-factors, we discuss the 6-edge-coloring strategies of bridgeless cubic graphs with different cycle core structures by cases, through the method of constructing a main coloring and extending it to the entire graph step by step. We study non-trivial snarks with a coloring defect number of at most 5, and prove that there exists a proper 6-edge-coloring such that there is at most one abnormal edge.