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
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.