Broadcast chromatic numbers of graphs

被引：0

作者：

Goddard, Wayne ^{[1
]}

Hedetniemi, Sandra M. ^{[1
]}

Hedetniemi, Stephen T. ^{[1
]}

Harris, John M. ^{[2
]}

Rall, Douglas F. ^{[2
]}

机构：

[1] Clemson Univ, Dept Comp Sci, Clemson, SC 29634 USA

[2] Furman Univ, Greenville, SC 29613 USA

来源：

ARS COMBINATORIA | 2008年 / 86卷

关键词：

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A function pi : V -> {1,..., k} is a broadcast coloring of order k if pi(u) = pi(v) implies that the distance between a and v is more than pi(u). The minimum order of a broadcast coloring is called the broadcast chromatic number of G; and is denoted chi(b)(G). In this paper we introduce this coloring and study its properties. In particular, we explore the relationship with the vertex cover and chromatic numbers. While there is a polynomial-time algorithm to determine whether chi(b)(G) <= 3, we show that it is NP-hard to determine if chi(b)(G) <= 4. We also determine the maximum broadcast chromatic number of a tree, and show that the broadcast chromatic number of the infinite grid is finite.

引用

页码：33 / 49

页数：17