Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 4 | 747-757

Tytuł artykułu

The B-Domatic Number of a Graph

Autorzy

Treść / Zawartość

Warianty tytułu

Języki publikacji

EN

Abstrakty

EN
Besides the classical chromatic and achromatic numbers of a graph related to minimum or minimal vertex partitions into independent sets, the b-chromatic number was introduced in 1998 thanks to an alternative definition of the minimality of such partitions. When independent sets are replaced by dominating sets, the parameters corresponding to the chromatic and achromatic numbers are the domatic and adomatic numbers d(G) and ad(G). We introduce the b-domatic number bd(G) as the counterpart of the b-chromatic number by giving an alternative definition of the maximality of a partition into dominating sets. We initiate the study of bd(G) by giving some properties and examples.

Wydawca

Rocznik

Tom

33

Numer

4

Strony

747-757

Opis fizyczny

Daty

wydano
2013-09-01
online
2013-10-15

Twórcy

  • LRI, UMR 8623, University Paris-Sud and CNRS F-91405 Orsay cedex, France

Bibliografia

  • [1] M. Alkhateeb and A. Kohl, Upper bounds on the b-chromatic number and results for restricted graph classes, Discuss. Math. Graph Theory 31 (2011) 709-735. doi:10.7151/dmgt.1575[Crossref]
  • [2] D. Barth, J. Cohen and T. Faik, Non approximality and non-continuity of the fall coloring problem, LRI Research report, Paris-Sud University 1402 (2005).
  • [3] S. Cabello and M. Jakovac, On the b-chromatic number of regular graphs, Discrete Appl. Math. 159 (2011) 1303-1310. doi:10.1016/j.dam.2011.04.028[Crossref][WoS]
  • [4] E.J. Cockayne, Domination in undirected graphs-a survey, in: Theory and Applications of Graphs, Lectures Notes in Math. 642, (Springer, Berlin, 1978) 141-147. doi:10.1007/BFb0070371[Crossref]
  • [5] E.J. Cockayne, and S.T. Hedetniemi, Disjoint independent dominating sets in graphs, Discrete Math. 15 (1976) 213-222. doi:10.1016/0012-365X(76)90026-1[WoS][Crossref]
  • [6] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977) 247-261. doi:10.1002/net.3230070305[Crossref]
  • [7] G.J. Chang, The domatic number problem, Discrete Math. 125 (1994) 115-122. doi:10.1016/0012-365X(94)90151-1[Crossref]
  • [8] S. Corteel, M. Valencia-Pabon and J.-C. Vera, On approximating the b-chromatic number , Discrete Appl. Math. 146 (2005) 106-110. doi:10.1016/j.dam.2004.09.006[Crossref]
  • [9] J.E. Dunbar, S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, J. Knisley, R.C. Laskar and D.F. Rall, Fall colorings in graphs, J. Combin. Math. Combin. Comput. 33 (2000) 257-273.
  • [10] F. Harary, S.T. Hedetniemi and G. Prins, An interpolation theorem for graphical homomorphisms, Port. Math. 26 (1967) 453-462.
  • [11] F. Harary and S.T. Hedetniemi, The achromatic number of a graph, J. Combin. Theory 8 (1970) 154-161. doi:10.1016/S0021-9800(70)80072-2[Crossref]
  • [12] C.T. Hoang, F. Maffray and M. Mechebbek, A characterization of b-perfect graphs, J. Graph Theory 71 (2012) 95-122. doi:10.1002/jgt.20635[Crossref]
  • [13] R.W. Irving and D.F. Manlove, The b-chromatic number of a graph, Discrete Appl. Math. 91 (1999) 127-141. doi:10.1016/S0166-218X(98)00146-2[WoS][Crossref]
  • [14] J. Ivančo, An interpolation theorem for partitions which are indivisible with respect to cohereditary properties, J. Combin. Theory (B) 52 (1991) 97-101. doi:10.1016/0095-8956(91)90095-2[Crossref]
  • [15] M. Kouider and M. Mahéo, Some bounds for the b-chromatic number of a graph, Discrete Math. 256 (2002) 267-277. doi:10.1016/S0012-365X(01)00469-1[Crossref]
  • [16] J. Kratochvíl, Zs. Tuza and M. Voigt, On the b-chromatic number of graphs, Lect. Notes Comput. Sci. 2573 (2002) 310-320. doi:10.1007/3-540-36379-3 27[Crossref]
  • [17] J. Lyle, N. Drake and R. Laskar, Independent domatic partitioning or fall coloring of strongly chordal graphs, Congr. Numer. 172 (2005) 149-159.
  • [18] D.F. Manlove, Minimaximal and maximinimal optimisation problems: a partial order approach (PhD Thesis, Glasgow, 1998).
  • [19] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ., 38, Providence, 1962).
  • [20] M. Valencia-Pabon, Idomatic partitions of direct products of complete graphs, Discrete Math. 310 (2010) 1118-1122. doi:10.1016/j.disc.2009.10.012[WoS][Crossref]
  • [21] B. Zelinka, Adomatic and idomatic numbers of graphs, Math. Slovaca 33 (1983) 99-103.
  • [22] B. Zelinka, Domatically critical graphs, Czechoslovak Math. J. 30 (1980) 486-489.

Typ dokumentu

Bibliografia

Identyfikatory

Identyfikator YADDA

bwmeta1.element.doi-10_7151_dmgt_1709
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ć.