PDF
Discussiones Mathematicae Graph Theory 30(3) (2010)
385-391
DOI: https://doi.org/10.7151/dmgt.1501
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
Close