On the Acyclic Chromatic Number of Hamming Graphs

被引：0

作者：

Robert E. Jamison

Gretchen L. Matthews

机构：

[1] University of Haifa,Department of Mathematical Sciences

[2] Clemson University,undefined

来源：

Graphs and Combinatorics | 2008年 / 24卷

关键词：

Acyclic coloring; Cartesian product of graphs; Distance 2 coloring; Hamming graph;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

An acyclic coloring of a graph G is a proper coloring of the vertex set of G such that G contains no bichromatic cycles. The acyclic chromatic number of a graph G is the minimum number k such that G has an acyclic coloring with k colors. In this paper, acyclic colorings of Hamming graphs, products of complete graphs, are considered. Upper and lower bounds on the acyclic chromatic number of Hamming graphs are given.

引用

页码：349 / 360

页数：11

共 25 条

[1]

Alon N.(1991)Acyclic colorings of graphs Random Structures Algorithms 2 277-288

[2]

McDiarmid C.(1996)On acyclic colorings of graphs on surfaces Israel J. Math. 94 273-283

[3]

Reed B.(1977)The triply shortened binary Hamming code is optimal Discrete Math. 17 235-245

[4]

Alon N.(1979)On acyclic colorings of planar graphs Discrete Math. 25 211-236

[5]

Mohar B.(1979)Every 4-valent graph has an acyclic 5-coloring Soobšč Akad. Nauk Gruzin SSR 93 21-24

[6]

Sanders D.P.(2003)Acyclic and k-distance coloring of the grid Inform. Process. Lett. 87 51-58

[7]

Best M.R.(1973)Acylic colorings of planar graphs Isreal J. Math. 14 390-408

[8]

Brouwer A.E.(2006)Acyclic colorings of products of trees Inform. Process. Lett. 99 7-12

[9]

Borodin O.V.(2005)Acyclic colorings of locally planar graphs European J. Combin. 26 491-503

[10]

Burnstein M.I.(2002)New bounds on a hypercube coloring problem Inform. Process. Lett. 84 265-269

← 1 2 3 →