Geodesic
Equitable Colorings Of Corona Multiproducts Of Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 1079-1094.

Voir la notice de l'article provenant de la source Library of Science

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by χ=(G). It is known that the problem of computation of χ=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts of graphs. In particular, we obtain some results regarding the equitable chromatic number for the l-corona product G ◦l H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs are mostly constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G. Moreover, we confirm the Equitable Coloring Conjecture for corona products of such graphs. This paper extends the results from [H. Furmánczyk, K. Kaliraj, M. Kubale and V.J. Vivin, Equitable coloring of corona products of graphs, Adv. Appl. Discrete Math. 11 (2013) 103–120].
Keywords: corona graph, equitable chromatic number, equitable coloring conjecture, equitable graph coloring, multiproduct of graphs, NP-completeness, polynomial algorithm 
@article{DMGT_2017_37_4_a16,
     author = {Furm\'anczyk, Hanna and Kubale, Marek and Mkrtchyan, Vahan V.},
     title = {Equitable {Colorings} {Of} {Corona} {Multiproducts} {Of} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1079--1094},
     publisher = {mathdoc},
     volume = {37},
     number = {4},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a16/}
}
TY  - JOUR
AU  - Furmánczyk, Hanna
AU  - Kubale, Marek
AU  - Mkrtchyan, Vahan V.
TI  - Equitable Colorings Of Corona Multiproducts Of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 1079
EP  - 1094
VL  - 37
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a16/
LA  - en
ID  - DMGT_2017_37_4_a16
ER  - 
%0 Journal Article
%A Furmánczyk, Hanna
%A Kubale, Marek
%A Mkrtchyan, Vahan V.
%T Equitable Colorings Of Corona Multiproducts Of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 1079-1094
%V 37
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a16/
%G en
%F DMGT_2017_37_4_a16
Furmánczyk, Hanna; Kubale, Marek; Mkrtchyan, Vahan V. Equitable Colorings Of Corona Multiproducts Of Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 1079-1094. http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a16/

[1] H.L. Bodleander and F.V. Fomin, Equitable colorings of bounded treewidth graphs, Theoret. Comput. Sci. 349 (2005) 22-30. doi: 10.1016/j.tcs.2005.09.027

[2] B.L. Chen, M.T. Ko and K.W. Lih, Equitable and m-bounded coloring of split graphs, in: Combinatorics and Computer Science, Lecture Notes in Comput. Sci. 1120 (1996) 1-5. doi: 10.1007/3-540-61576-8 67

[3] B.L. Chen, K.W. Lih and P.L. Wu, Equitable coloring and the maximum degree, European J. Combin. 15 (1994) 443-447. doi: 10.1006/eujc.1994.1047

[4] R. Frucht and F. Harary, On the corona of two graphs, Aequationes Math. 4 (1970) 322-325. doi: 10.1007/BF01844162

[5] H. Furmánczyk, Equitable coloring of graphs, in: M. Kubale, Ed., Graph Colorings (American Mathematical Society, Providence, Rhode Island, 2004). doi: 10.1090/conm/352/03

[6] H. Furmánczyk, Equitable coloring of graph products, Opuscula Math. 26 (2006) 31-44.

[7] H. Furmánczyk, K. Kaliraj, M. Kubale and V.J. Vivin, Equitable coloring of corona products of graphs, Adv. Appl. Discrete Math. 11 (2013) 103-120.

[8] H. Furmánczyk and M. Kubale, Equitable coloring of corona products of cubic graphs is harder than ordinary coloring, Ars Math. Contemp. 10 (2016) 333-347.

[9] H. Furmánczyk and M. Kubale, Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines, Discrete Appl. Math. (2017), in press. doi: 10.1016/j.dam.2016.01.036

[10] A. Hajnal, E. Szemeredi, Proof of a conjecture of Erd¨os, in: Combinatorial Theory and Its Applications, II, Colloq. Math. Soc. János Bolyai, 4 (North-Holland, Amsterdam, 1970).

[11] H.A. Kierstead, A.V. Kostochka, M. Mydlarz and E. Szemeredi, A fast algorithm for equitable coloring, Combinatorica 30 (2010) 217-224. doi: 10.1007/s00493-010-2483-5

[12] K.W. Lih, Equitable coloring of graphs, in: Handbook of Combinatorial Optimization (Springer, New York, 2013) 1199-1248. doi: 10.1007/978-1-4419-7997-1 25

[13] K.W. Lih and P.L. Wu, On equitable coloring of bipartite graphs, Discrete Math. 151 (1996) 155-160. doi: 10.1016/0012-365X(94)00092-W

[14] W.H. Lin and G.J. Chang, Equitable colorings of Cartesian products of graphs, Discrete Appl. Math. 160 (2012) 239-247. doi: 10.1016/j.dam.2011.09.020

[15] W. Meyer, Equitable coloring, Amer. Math. Monthly 80 (1973) 920-922. doi: 10.2307/2319405

[16] K. Nakprasit, Equitable colorings of planar graphs with maximum degree at least nine, Discrete Math. 312 (2012) 1019-1024. doi: 10.1016/j.disc.2011.11.004

[17] W. Wang and K. Zhang, Equitable colorings of line graphs and complete r-partite graphs, Systems Sci. Math. Sci. 13 (2000) 190-194.

[18] H.P. Yap and Y. Zhang, The Equitable Δ-Coloring Conjecture holds for outerplanar graphs, Bull. Inst. Math. Acad. Sin. 25 (1997) 143-149.

[19] H.P. Yap and Y. Zhang, Equitable colorings of planar graphs, J. Combin. Math. Combin. Comput. 27 (1998) 97-105.

[20] X. Zhang and J.-L. Wu, On equitable and equitable list colorings of series-parallel graphs, Discrete Math. 311 (2011) 800-803. doi: 10.1016/j.disc.2011.02.001