Abstract | ||
---|---|---|
A proper k-coloring with colors 1,2,…,k of a graph G=(V,E) is an ordered partition (V1,V2,…,Vk) of V such that Vi is an independent set or color class in which each vertex v∈Vi is assigned color i for 1≤i≤k. A vertex v∈Vi is a Grundy vertex if it is adjacent to at least one vertex in each color class Vj for every j,j<i. A proper coloring is a partial Grundy coloring if every color class has at least one Grundy vertex in it and the partial Grundy number, denoted as ∂Γ(G), is the maximum number of colors used in a partial Grundy coloring. Given a graph G and an integer k,1≤k≤n, the Partial Grundy Number Decision Problem is to decide whether ∂Γ(G)≥k. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1016/j.dam.2019.08.005 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Partial Grundy coloring,Perfect elimination bipartite graphs,Star-convex bipartite graphs,Chordal graphs,NP-completeness,Polynomial time algorithms | Journal | 271 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
B. S. Panda | 1 | 99 | 21.18 |
Shaily Verma | 2 | 0 | 0.34 |