Geodesic
Fall coloring of graphs I
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 3, pp. 385-391

Voir la notice de l'article provenant de la source Library of Science

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 
Balakrishnan, Rangaswami; Kavaskar, T. Fall coloring of graphs I. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 3, pp. 385-391. http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a2/
@article{DMGT_2010_30_3_a2,
     author = {Balakrishnan, Rangaswami and Kavaskar, T.},
     title = {Fall coloring of graphs {I}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {385--391},
     year = {2010},
     volume = {30},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a2/}
}
TY  - JOUR
AU  - Balakrishnan, Rangaswami
AU  - Kavaskar, T.
TI  - Fall coloring of graphs I
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 385
EP  - 391
VL  - 30
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a2/
LA  - en
ID  - DMGT_2010_30_3_a2
ER  - 
%0 Journal Article
%A Balakrishnan, Rangaswami
%A Kavaskar, T.
%T Fall coloring of graphs I
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 385-391
%V 30
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a2/
%G en
%F DMGT_2010_30_3_a2

[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.