PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2010 | 30 | 3 | 385-391
Tytuł artykułu

Fall coloring of graphs I

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
30
Numer
3
Strony
385-391
Opis fizyczny
Daty
wydano
2010
otrzymano
2009-03-18
poprawiono
2009-07-27
zaakceptowano
2009-08-17
Twórcy
  • Srinivasa Ramanujan Centre, SASTRA University, Kumbakonam - 612 001, India
autor
  • Srinivasa Ramanujan Centre, SASTRA University, Kumbakonam - 612 001, India
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1501
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.