On Fall Colorings Of Graphs

A coloring of a graph G = (V, E") is a partition II = {V1, V2, ??? Vk} of the vertices of G into independent sets or color classes. A vertex v Vi is called colorful if it is adjacent to at least one vertex in every color class Vj,i j. A fall coloring is a coloring in which every vertex is colorful. If a graph has a fall coloring, we define the fall chromatic number(fall achromatic number) of G, denoted Xf(G)(f(G)) to equal the minimum (maximum) numbers of colors used in a fall coloring of G, respectively. In this paper we study fall coloring of Cartesian Products and get some results on the fall colorings of regular graphs. Then we consider the relation of fall coloring and perfect graph. Last we study the charactistic of fall coloring and the difference between Xf(G) and x(G).