QA305 : Grundy number in graphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2015
Authors:
Fatemeh Rezamohammadi [Author], Meysam Alishahi[Supervisor]
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 ‎algorithm‎s 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 ‎obtain‎ed 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 Link
Keeping place: Central Library of Shahrood University
Visitor: