An algorithm for partial Grundy number on trees

A coloring of a graph G = ( V , E ) is a partition { V 1 , V 2 , … , V k } of V into independent sets or color classes. A vertex v ∈ V i is a Grundy vertex if it is adjacent to at least one vertex in each color class V j for every j < i . A coloring is a partial Grundy coloring if every color cla...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2005-11, Vol.304 (1), p.108-116
Main Authors: Shi, Zhengnan, Goddard, Wayne, Hedetniemi, Stephen T., Kennedy, Ken, Laskar, Renu, McRae, Alice
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Graph algorithms
Graph theory
Information retrieval. Graph
Linear algorithms
Mathematics
Partial Grundy coloring
Sciences and techniques of general use
Theoretical computing
Tree
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A coloring of a graph G = ( V , E ) is a partition { V 1 , V 2 , … , V k } of V into independent sets or color classes. A vertex v ∈ V i is a Grundy vertex if it is adjacent to at least one vertex in each color class V j for every j < i . A coloring is a partial Grundy coloring if every color class contains at least one Grundy vertex, and the partial Grundy number of a graph is the maximum number of colors in a partial Grundy coloring. We derive a natural upper bound on this parameter and show that graphs with sufficiently large girth achieve equality in the bound. In particular, this gives a linear-time algorithm to determine the partial Grundy number of a tree.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2005.09.008