# Fall coloring of graphs I

Rangaswami Balakrishnan; T. Kavaskar

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 3, page 385-391
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topRangaswami Balakrishnan, and T. Kavaskar. "Fall coloring of graphs I." Discussiones Mathematicae Graph Theory 30.3 (2010): 385-391. <http://eudml.org/doc/270859>.

@article{RangaswamiBalakrishnan2010,

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.},

author = {Rangaswami Balakrishnan, T. Kavaskar},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {fall coloring of graphs; non-fall colorable graphs; color dominating vertex},

language = {eng},

number = {3},

pages = {385-391},

title = {Fall coloring of graphs I},

url = {http://eudml.org/doc/270859},

volume = {30},

year = {2010},

}

TY - JOUR

AU - Rangaswami Balakrishnan

AU - T. Kavaskar

TI - Fall coloring of graphs I

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 3

SP - 385

EP - 391

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

LA - eng

KW - fall coloring of graphs; non-fall colorable graphs; color dominating vertex

UR - http://eudml.org/doc/270859

ER -

## References

top- [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). Zbl0938.05001
- [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. Zbl0962.05020
- [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. Zbl1156.05020

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.