QA305 : Grundy number in graphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2015
Authors:
Abstarct: Given a graph G = (V, E) , a k-coloring of G is an assignment of k colors to the vertices of G in such a way that adjacent vertices have distinct colors. the chromatic number of G , χ(G) , is the minimum integer k such that G admits a k-coloring. the problem of determining χ(G) is NP-hard. therefore the evaluation of the performance of fast vertex coloring algorithms is a relevant problem. the greedy coloring algorithm is a linear vertex coloring algorithm. given an order θ=v1,...,vn over V, the greedy algorithm to color the vertices of G assigns to vi the minimum positive integer that was not already assigned to its neighbors in the set {v1 ,…,vi-1.{ a coloring obtained by an execution of this algorithm is usually called as a greedy coloring. the maximum number of colors of a greedy coloring of a graph G, over all the orders θ of V(G), is the Grundy number of G and it is denoted by Γ(G).
In chapter 1, we review theory graph concepts that we need them in the future chapters.
In chapter 2, we represent game grundy number concepts in graphs and we prove some theorems about it.
In chapter 3, we represent some results on grundy number.
In chapter 4, we represent some upper bounds for the grundy number of product graphs.
Keywords:
#Greedy coloring #Grundy number #The game grundy number #Product graphs
Keeping place: Central Library of Shahrood University
Visitor:
Keeping place: Central Library of Shahrood University
Visitor: