The Color-Character Of Regular Graphs Of Class 2

By Vizing's theorem, k-regular simple graphs can be classified into two classes. Graphs with chromatic index k are Class 1 and with chromatic index k + 1 are Class 2. It is easy to prove some problems for graphs of Class 1, but those problems become extremely hard when we consider them for graphs of Class 2. The most interesting is cubic (3-regular) graphs of Class 2. Some famous conjectures, e.g. Tutte's 5-flow Conjecture,the Cycle Double Cover Conjecture (CDCC) (see [1],[2]), are obstructed by cubic graphs of Class 2. Moreover, the Four-Color Theorem is equivalent to the statement that every bridgeless cubic planar graph is 3-colorable (see [3],[4]). Motivated by these researches we focus our intention on the study of regular graphs of Class 2.So we consider a parameter—color-character of regular graphs of Class 2. Let G be a k-regular graph of Class 2. Suppose c is a proper (k+1)-edge-coloring of G and E_i = {e ∈ E | c(e) = i}, i = 0,1,..., k. Let o(c) = min{|E_i| | i =0,1, ... , k} and define m(G) = (c∈C(G))|(min){o(c)} to be the color-character of G, where C(G) consists of all the proper (k + l)-edge-colorings of G. And we define the color-character of k-regular graphs (may have multiple edges) with chromatic index k + 1 in the same way. Intuitively, m(G) is the minimum number of edges which have to be removed from G to obtain a graph with chromatic index k. The color-character provides a way to classify k-regular graphs of Class 2. So it enables us to study those graphs class by class, especially to verify the famous conjectures. Therefore, in this paper, we consider the properties of color-character of regular graphs of Class 2.For cubic graphs, we obtain the following results.Let G be a cubic graph. If x'(G) =3, then define m(G) = 0, we have1. Suppose G₁ is a subgraph of G, x'(G₁) = 3 and the edges betweenV(G₁) and V(G₁) form a 3-edge-cut of G, then the graph obtained from G by contracting G₁ into one vertex has the same color-character as G.2. m(G) is an invariant under Δ-reduction and m(G) ≤ |V(G)|/5 if G has...