2009/09/15 by Saeed Shaebani, Shaebani, Saeed
Mathematics · #05C #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C
paper · pdf · doi:10.48550/arxiv.0909.2769
arxiv created 2009/09/15 · arxiv updated 2009/12/01
A fall k-coloring of a graph G is a proper k-coloring of G such that each vertex of G sees all k colors on its closed neighborhood. We denote \rm Fall(G) the set of all positive integers k for which G has a fall k-coloring. In this paper, we study fall colorings of lexicographic product of graphs and categorical product of graphs and answer a question of \citedun about fall colorings of categorical product of complete graphs. Then, we study fall colorings of union of graphs. Then, we prove that fall k-colorings of a graph can be reduced into proper k-colorings of graphs in a specified set. Then, we characterize fall colorings of Mycielskian of graphs. Finally, we prove that for each bipartite graph G, \rm Fall(Gc)⊆ \χ(Gc) \ and it is polynomial time to decision whether or not \rm Fall(Gc)=\χ(Gc) \.