Borodin-Kostochka's Conjecture on {P2 ∨ P3, C4}-Free Graphs - Details

author：

Lan, Kaiyang (Lan, Kaiyang.) ^[1] | Liu, Feng (Liu, Feng.) ^[2] | Zhou, Yidong (Zhou, Yidong.) ^[3]

Indexed by：

Scopus SCIE

Abstract：

Let　P-n　and　C-n　denote　the　induced　path　and　cycle　on　n　vertices,　respectively.　For　two　graphs　H-1　and　H-2,　we　use　H-1　boolean　OR　H-2　to　denote　the　graph　with　vertex　set　V(H-1)　boolean　OR　V(H-2)　and　edge　set　E(H-1)　boolean　OR　E(H-2).　Let　Delta　(G),　chi(G)　and　omega(G)　denote　the　maximum　degree,　chromatic　number　and　clique　number　of　G,　respectively.　The　Borodin-Kostochka　Conjecture　states　that　for　a　graph　G,　if　Delta(G)　＞=　9,　then　chi(G)　＜=　max{Delta(G)　-1,　omega(G)}.　In　this　paper,　we　prove　the　conjecture　for　{P-2　boolean　OR　P-3,　C-4}-free　graphs.

Keyword：

Borodin-Kostochka conjecture Chromatic number Induced subgraphs

Community：

[ 1 ] [Lan, Kaiyang]Minnan Normal Univ, Sch Math & Stat, Zhangzhou 363000, Fujian, Peoples R China
[ 2 ] [Liu, Feng]East China Normal Univ, Dept Math, Shanghai 200241, Peoples R China
[ 3 ] [Zhou, Yidong]Nankai Univ, Coll Comp Sci, Tianjin 300350, Peoples R China
[ 4 ] [Lan, Kaiyang]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China
[ 5 ] [Zhou, Yidong]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China