On the Dynamic Coloring of Cartesian Product Graphs

被引:0
作者
Akbari, S. [1 ,2 ]
Ghanbari, M. [1 ]
Jahanbekam, S. [1 ]
机构
[1] Sharif Univ Technol, Dept Math Sci, Tehran, Iran
[2] Inst Res Fundamental Sci IPM, Sch Math, Tehran, Iran
关键词
Dynamic coloring; Cartesian product of graphs;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G and H be two graphs. A proper vertex coloring of G is called a dynamic coloring, if for every vertex v with degree at least 2, the neighbors of v receive at least two different colors. The smallest integer k such that G has a dynamic coloring with k colors denoted by chi(2)(G). We denote the cartesian product of G and H by G square H. In this paper, we prove that if G and H are two graphs and delta(G) >= 2, then chi(2)(G square H) <= max(chi(2)(G), chi(H)). We show that for every two natural numbers m and n, m, n >= 2, chi(2) (P-m square P-n) = 4. Also, among other results it is shown that if 3 vertical bar mn, then chi(2)(C-m square C-n) = 3 and otherwise chi(2) (C-m square C-n) = 4.
引用
收藏
页码:161 / 168
页数:8
相关论文
共 4 条
  • [1] AKBARI S, ARS COMBIN IN PRESS
  • [2] Lai HJ, 2003, ARS COMBINATORIA, V68, P193
  • [3] Conditional colorings of graphs
    Lai, Hong-Jian
    Lin, Jianliang
    Montgomery, Bruce
    Shui, Taozhi
    Fan, Suohai
    [J]. DISCRETE MATHEMATICS, 2006, 306 (16) : 1997 - 2004
  • [4] Montgomery B., 2001, Dynamic coloring of graphs