On Fall Colorings of Graphs

Details On Fall Colorings of Graphs On Fall Colorings of Graphs

2009-09-15

arxiv.org/abs/0909.2769v1

Mathematics

Combinatorics

Scientific paper

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 \cite{dun} 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}(G^{c})\subseteq \{\chi (G^{c}) \}$ and it is polynomial time to decision whether or not ${\rm Fall}(G^{c})=\{\chi (G^{c}) \}$.

Affiliated with

Also associated with

No associations

Rating

On Fall Colorings of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Fall Colorings of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Fall Colorings of Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-555845