On the average degree of edge chromatic critical graphs
On the average degree of edge chromatic critical graphs
复制标题
DOI：
10.1016/j.jctb.2020.04.004
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Yan Cao;Guantao Chen
中科院分区：
文献类型：
--
作者：
Yan Cao;Guantao Chen
设G是一个简单图，χ‘(G)和Δ(G)分别表示G的色数和最大度。图G是临界二类图，如果对G的每个真子图H有χ‘(G)=Δ(G)+1和χ’(H)≤Δ(G).设d‾(G)表示G的平均度，即d‾(G)=2|E(G)|/|V(G)|.Visting在1968年猜想，如果G是n阶临界二类图，则d‾(G)≥Δ(G)−1+3/n.本文证明了如果G是临界二类图，d‾(G)≥3 4Δ(G)−8.设δ(G)表示G的最小度，证明了存在两个函数D和D0，使得对于任意ϵ∈(0，1)，如果G是一个临界二类图，且有Δ(G)≥D(ϵ)和δ(G)≥D0(ϵ)，则d‾(G)≥(1−ϵ)Δ(G)).在本文中，我们将给出两个满足上述陈述的具体函数。此外，如果G是临界二类图，且δ(G)≥(logΔ(G))34，则d‾(G)≥Δ(G)−o(Δ(G))。
Let G be a simple graph, and let χ′(G) and Δ (G) denote the chromatic index and the maximum degree of G, respectively. A graph G is a critical class two graph if χ′(G)= Δ (G)+ 1 and χ′(H)≤ Δ (G) for every proper subgraph H of G. Let d‾(G) denote the average degree of G, ie, d‾(G)= 2| E (G)|/| V (G)|. Vizing in 1968 conjectured that d‾(G)≥ Δ (G)− 1+ 3/n if G is a critical class two graph of order n. In this paper, we prove that d‾(G)≥ 3 4 Δ (G)− 8 if G is a critical class two graph. Let δ (G) denote the minimum degree of G. We show that there exist two functions D and D 0 such that for any ϵ∈(0, 1), if G is a critical class two graph with Δ (G)≥ D (ϵ) and δ (G)≥ D 0 (ϵ), then d‾(G)≥(1− ϵ) Δ (G). We will give two specific functions satisfying the statement above in the paper. Moreover, we show that if G is a critical class two graph and δ (G)≥(log Δ (G)) 3 4, then d‾(G)≥ Δ (G)− o (Δ (G)).