Relations between the domination parameters and the chromatic index of a graph
Włodzimierz Ulatowski
Discussiones Mathematicae Graph Theory, Tome 29 (2009), p. 615-627 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

In this paper we show upper bounds for the sum and the product of the lower domination parameters and the chromatic index of a graph. We also present some families of graphs for which these upper bounds are achieved. Next, we give a lower bound for the sum of the upper domination parameters and the chromatic index. This lower bound is a function of the number of vertices of a graph and a new graph parameter which is defined here. In this case we also characterize graphs for which a respective equality holds.

Publié le : 2009-01-01
EUDML-ID : urn:eudml:doc:270801 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1468,
     author = {W\l odzimierz Ulatowski},
     title = {Relations between the domination parameters and the chromatic index of a graph},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {29},
     year = {2009},
     pages = {615-627},
     zbl = {1194.05119},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1468}
}

Włodzimierz Ulatowski. Relations between the domination parameters and the chromatic index of a graph. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 615-627. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1468/

[000] [1] M. Chellalia and L. Volkmann, Relations between the lower domination parameters and the chromatic number of a graph, Discrete Math. 274 (2004) 1-8, doi: 10.1016/S0012-365X(03)00093-1.

[001] [2] E.J. Cockayne, O. Favaron, C. Payan and A.G. Thomas, Contributions to the theory of domination, independence and irredundance in graphs, Discrete Math. 33 (1981) 249-258, doi: 10.1016/0012-365X(81)90268-5.

[002] [3] O. Favaron, Stability, domination and irredundance in a graph, J. Graph Theory 10 (1986) 429-438, doi: 10.1002/jgt.3190100402. | Zbl 0612.05056

[003] [4] T. Gallai, Über extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 2 (1959) 133-138. | Zbl 0094.36105

[004] [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Decker Inc., New York, 1998). | Zbl 0890.05002

[005] [6] D. König, Graphok és alkalmazásuk a determinánsok és a halmazok elméletére, Math. Termész. Ért. 34 (1916) 104-119. | Zbl 46.1451.03

[006] [7] D. König, Graphs and matrices, Mat. Fiz. Lapok 38 (1931) 116-119 (in Hungarian).

[007] [8] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Metody Diskret. Analiz. 29 (1964) 25-30 (in Russian).