QA266 : Dynamic Coloring Of Graphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2014
Authors:
Abstarct: A k-dynamic coloring of a graph G is a proper coloring of G with k colors such
that for every vertex v ∈ V (G) of degree at least 2, the neighbors of v receive at
least 2 colors. The dynamic chromatic number of a graphG, χ2(G), is the least
number k such that G admits a k-dynamic coloring. B. Montgomery in his Ph.D.
Thesis intruduced dynamic chromatic number and conjectured that the difference between chromatic and dynamic chromatic number of regular graphs is at
most 2. Recently, this conjecture has been studied in several papers. M. Alishahi
proved that the difference between chromatic and dynamic chromatic number of
a k-regular graphs is at most O(ln k). Also, He presented an upper bound for the
dynamic chromatic number of a regular graph in terms of chromatic number of
graph and independence number of second power of the graph.
In this thesis, we study the relationship between the chromatic number and dynamic chromatic number of graphs. Alos, we intrduce the list dynamic chromatic
number of graphs and present some results about this parameter.
Keywords:
#Dynamic chromatic number #Dynamic list chromatic number #Total dominating set #Hypergraph coloring #Incidence graph
Keeping place: Central Library of Shahrood University
Visitor:
Keeping place: Central Library of Shahrood University
Visitor: