One Inequality about the Relation between the Maximum Degree and Chromatic Number of Colour-Critical Graphs
Shu Qing · Shuxue de shijian yu renshi · 2012
In this paper,the relation between the chromatic number x(G) and maximum degreeΔ(G) of some given graphs G is researched.Let G be a(x(G) + s)-order colour-critical graph with x(G) s~2+s/2,this paper proves thatΔ(G) = x(G) + s—1 or equivalentlyΔ(G) + 1 -[8Δ(G)+17~(1/2)-3/2]≤x(G)≤Δ(G) + 1,which partly improves a classical result due to Brooks as follow:x(G)≤Δ(G) + 1.And completely characterizes the structure of n-critical graph with order of n + 3(n≥4).