On Fall-Colorable Graphs

A fall k -coloring of a graph G is a proper k -coloring of G such that each vertex has at least one neighbor in each of the other color classes. A graph G which has a fall k -coloring is equivalent to having a partition of the vertex set V ( G ) in k independent dominating sets. In this paper, we first prove that for any fall k -colorable graph G with order n , the number of edges of G is at least ( n ( k − 1 ) + r ( k − r ) ) / 2 , where r ≡ n ( mod k ) and 0 ≤ r ≤ k − 1 , and the bound is tight. Then, we obtain that if G is k -colorable ( k ≥ 2 ) and the minimum degree of G is at least k − 2 k − 1 n , then G is fall k -colorable and this condition of minimum degree is the best possible. Moreover, we give a simple proof for an NP-hard result of determining whether a graph is fall k -colorable, where k ≥ 3 . Finally, we show that there exist an infinite family of fall k -colorable planar graphs for k ∈ { 5 , 6 } .