|
|||||
|
|
On the equality of the partial Grundy and upper ochromatic numbers of graphs |
|
| Authors: | Paul Erdös Stephen T Hedetniemi Renu C Laskar |
| Institution: | a Hungarian Academy of Sciences, Mathematical Institute, Budapest, Hungary b Department of Computer Science, Clemson University, Clemson, SC 29634, USA c Department of Mathematical Sciences, Clemson University, Clemson, SC 29634, USA d Department of Mathematics, Wayne State University, Detroit, MI 48202, USA |
| Abstract: | A (proper) k-coloring of a graph G is a partition Π={V1,V2,…,Vk} of V(G) into k independent sets, called color classes. In a k-coloring Π, a vertex v∈Vi is called a Grundy vertex if v is adjacent to at least one vertex in color class Vj, for every j, j<i. A k-coloring is called a Grundy coloring if every vertex is a Grundy vertex. A k-coloring is called a partial Grundy coloring if every color class contains at least one Grundy vertex. In this paper we introduce partial Grundy colorings, and relate them to parsimonious proper colorings introduced by Simmons in 1982. |
| Keywords: | Colorings Chromatic number Achromatic number Grundy number |
| 本文献已被 ScienceDirect 等数据库收录！ | |