QA266 : Dynamic Coloring Of Graphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2014
Authors:
Masoomeh Valizadeh Moghadam [Author], Meysam Alishahi[Supervisor], Seyed Reza Musawi[Advisor]
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 Link
Keeping place: Central Library of Shahrood University
Visitor: