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 of G is the minimum size of a fall color partition of G (when it exists). Trivially, for any graph G, . In this paper, we show the existence of an infinite family of graphs G with prescribed values for χ(G) and . 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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1501,
author = {Rangaswami Balakrishnan and T. Kavaskar},
title = {Fall coloring of graphs I},
journal = {Discussiones Mathematicae Graph Theory},
volume = {30},
year = {2010},
pages = {385-391},
zbl = {1217.05086},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1501}
}
Rangaswami Balakrishnan; T. Kavaskar. Fall coloring of graphs I. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 385-391. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1501/
[000] [1] G.E. Andrews, The Theory of Partitions (Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1998). Reprint of the 1976 original.
[001] [2] R. Balakrishnan and K. Ranganathan. A Textbook of Graph Theory (Universitext, Springer-Verlag, New York, 2000). | Zbl 0938.05001
[002] [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. | Zbl 0962.05020
[003] [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. | Zbl 1156.05020