The B-Domatic Number of a Graph

Odile Favaron

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 4, page 747-757
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Odile Favaron. "The B-Domatic Number of a Graph." Discussiones Mathematicae Graph Theory 33.4 (2013): 747-757. <http://eudml.org/doc/268011>.

@article{OdileFavaron2013,
abstract = {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.},
author = {Odile Favaron},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domatic number; adomatic number; b-domatic number; bchromatic number; idomatic number; partition; -domatic number; -chromatic number},
language = {eng},
number = {4},
pages = {747-757},
title = {The B-Domatic Number of a Graph},
url = {http://eudml.org/doc/268011},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Odile Favaron
TI - The B-Domatic Number of a Graph
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 4
SP - 747
EP - 757
AB - 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.
LA - eng
KW - domatic number; adomatic number; b-domatic number; bchromatic number; idomatic number; partition; -domatic number; -chromatic number
UR - http://eudml.org/doc/268011
ER -

References

top
  1. [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] Zbl1255.05072
  2. [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. [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] Zbl1223.05063
  4. [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. [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] Zbl0364.05035
  6. [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] Zbl0384.05051
  7. [7] G.J. Chang, The domatic number problem, Discrete Math. 125 (1994) 115-122. doi:10.1016/0012-365X(94)90151-1[Crossref] 
  8. [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] Zbl1057.05032
  9. [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. Zbl0962.05020
  10. [10] F. Harary, S.T. Hedetniemi and G. Prins, An interpolation theorem for graphical homomorphisms, Port. Math. 26 (1967) 453-462. Zbl0187.20903
  11. [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] Zbl0195.25702
  12. [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] Zbl1248.05073
  13. [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. [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] Zbl0741.05003
  15. [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. [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] Zbl1024.05026
  17. [17] J. Lyle, N. Drake and R. Laskar, Independent domatic partitioning or fall coloring of strongly chordal graphs, Congr. Numer. 172 (2005) 149-159. Zbl1088.05033
  18. [18] D.F. Manlove, Minimaximal and maximinimal optimisation problems: a partial order approach (PhD Thesis, Glasgow, 1998). 
  19. [19] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ., 38, Providence, 1962). 
  20. [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] Zbl1215.05136
  21. [21] B. Zelinka, Adomatic and idomatic numbers of graphs, Math. Slovaca 33 (1983) 99-103. Zbl0507.05059
  22. [22] B. Zelinka, Domatically critical graphs, Czechoslovak Math. J. 30 (1980) 486-489. 

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.