Discussiones Mathematicae Graph Theory 30(3) (2010) 385-391
doi: 10.7151/dmgt.1501

[BIBTex] [PDF] [PS]

FALL COLORING OF GRAPHS  I

Rangaswami Balakrishnan  and  T. Kavaskar

Srinivasa Ramanujan Centre
SASTRA University
Kumbakonam - 612 001, India
e-mail: mathbala@satyam.net.in
e-mail: t_kavaskar@yahoo.com

Abstract

A fall coloring of a graph G is a proper coloring of the vertex set of G such that every vertex of G is a color dominating vertex in G (that is, it has at least one neighbor in each of the other color classes). The fall coloring number χf(G) of G is the minimum size of a fall color partition of G (when it exists). Trivially, for any graph G, χ(G) ≤ χf(G). In this paper, we show the existence of an infinite family of graphs G with prescribed values for χ(G) and χf(G). We also obtain the smallest non-fall colorable graphs with a given minimum degree δ and determine their number. These answer two of the questions raised by Dunbar et al.

Keywords: fall coloring of graphs, non-fall colorable graphs.

2010 Mathematics Subject Classification: 05C15.

References

[1] G.E. Andrews, The Theory of Partitions (Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1998). Reprint of the 1976 original.
[2] R. Balakrishnan and K. Ranganathan. A Textbook of Graph Theory (Universitext, Springer-Verlag, New York, 2000).
[3] J.E. Dunbar, S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, J. Knisely, R.C. Laskar and D.F. Rall, Fall colorings of graphs, J. Combin. Math. Combin. Comput. 33 (2000) 257-273. Papers in honour of Ernest J. Cockayne.
[4] R.C. Laskar and J. Lyle, Fall coloring of bipartite graphs and cartesian products of graphs, Discrete Appl. Math. 157 (2009) 330-338, doi: 10.1016/j.dam.2008.03.003.

Received 18 March 2009
Revised 27 July 2009
Accepted 17 August 2009