On the chromaticity of the 2-degree integral subgraph ofq-trees |
| |
Authors: | Xiaodong Li Xiangwu Liu |
| |
Institution: | 1. The Mathematics and Statistics School, Zhejiang University of Finance and Economics, 310018, Hangzhou, P. R. China 2. Department of Mathematics, Harbin Normal University, 150080, Harbin, P. R. China
|
| |
Abstract: | A graphG is called to be a 2-degree integral subgraph of aq-tree if it is obtained by deleting an edge e from an integral subgraph that is contained in exactlyq- 1 triangles. An added-vertexq-treeG with n vertices is obtained by taking two verticesu, v (u, v are not adjacent) in a q-treesT withn -1 vertices such that their intersection of neighborhoods ofu, v forms a complete graphK q , and adding a new vertexx, new edgesxu, xv, xv 1,xv 2, …,xv q- 4, where {v 1,v 2,...,v q?4} ?-K q . In this paper we prove that a graphG with minimum degree not equal toq -3 and chromatic polynomialP(G;λ) = λ(λ - 1) … (λ -q +2)(λ -q +1)3(λ -q) n- q- 2 withn ≥ q + 2 has and only has 2-degree integral subgraph of q-tree withn vertices and added-vertex q-tree withn vertices. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|