AN APPROACH TO HEDETNIEMIS CONJECTURE

被引:14
作者
SAUER, NW
ZHU, X
机构
[1] Department of Mathematics and Statistics, University of Calgary, Calgary, Alberta
关键词
D O I
10.1002/jgt.3190160504
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For a fixed integer n is-an-element-of omega, a graph G of chromatic number greater than n is called persistent if for all n + 1-chromatic graphs H, the products G X H are n + 1-chromatic graphs. Whether all graphs of chromatic number greater than n are persistent is a long-standing open problem due to Hedetniemi. We call a graph G strongly persistent if G is persistent and the Hajos sum of G with any other persistent graph H is still persistent. This paper extends the class of known persistent graphs by proving the following results: If G is constructed from copies of K(n+1) by Hajos sums, adding vertices and edges and at most one contraction of nonadjacent vertices, then G is strongly persistent.
引用
收藏
页码:423 / 436
页数:14
相关论文
共 22 条