Equitable colorings of l-corona products of cubic graphs

• Autorzy: Furmańczyk Hanna , Kubale Marek

Identyfikatory

DOI

10.24425/acs.2024.149658

• Języki publikacji: EN

Abstrakty

EN

A graph 𝐺 is equitably 𝑘-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest integer 𝑘 for which such a coloring exists is known as the equitable chromatic number of 𝐺 and it is denoted by _x=(𝐺). In this paper the problem of determining the value of equitable chromatic number for multicoronas of cubic graphs G ◦^l H is studied. The problem of ordinary coloring of multicoronas of cubic graphs is solvable in polynomial time. The complexity of equitable coloring problem is an open question for these graphs. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use at most _x=(G ◦^l H) + 1 colors in the remaining cases.

Słowa kluczowe

EN

corona graph; l-corona products; cubic graph; equitable chromatic number; polynomial algorithm; 1-absolute approximation algorithm

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2024
• Tom: Vol. 34, No. 1
• Strony: 211--223
• Opis fizyczny: Bibliogr. 19 poz., tab., wzory

Twórcy

autor

Furmańczyk Hanna

• Institute of Informatics, University of Gdańsk, Wita Stwosza 57, 80-308 Gdańsk, Poland

• https://orcid.org/0000-0001-8057-4108

autor

Kubale Marek

• Department of Algorithms and System Modelling, Gdańsk University of Technology, Narutowicza 11/12, 80-233 Gdańsk, Poland

• https://orcid.org/0000-0001-9460-3782

Bibliografia

• [1] R.L. Brooks: On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37 (1941), 194-197.
• [2] B.L. Chen, K.W. Lih and P.L. Wu: Equitable coloring and the maximum degree. European Journal of Combinatorics, 15(5), (1994), 443-447. DOI: 10.1006/eujc.1994.1047
• [3] B.L. Chen and C.H. Yen: Equitable Δ-coloring of graphs. Discrete Mathematics, 312(9), (2012), 1512-1517. DOI: 10.1016/j.disc.2011.05.020
• [4] G. Cordasco, L. Gargano and A.A. Rescigno: Iterated type partitions. Proceedings of 31st International Workshop, IWOCA 2020. In Lecture Notes in Computer Science: Combinatorial Algorithms, 12126 (2020), 195-210. DOI: 10.1007/978-3-030-48966-3_15
• [5] R. Frucht and F. Harary: On the corona of two graphs. Aequationes Mathematicae, 4 (1970), 322-325.
• [6] H. Furmańczyk, A. Jastrzębski and M. Kubale: Equitable coloring of graphs. Recent theoretical results and new practical algorithms. Archives of Control Sciences, 26(3), (2016), 281-295. DOI: 10.1515/acsc-2016-0016
• [7] H. Furmańczyk, K. Kaliraj, M. Kubale and V.J. Vivin: Equitable coloring of corona products of graphs. Advances and Applications of Discrete Mathematics, 11(2), (2013), 103-120.
• [8] H. Furmańczyk and M. Kubale: Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling. Archives of Control Sciences, 25(1), (2015), 109-116. DOI: 10.1515/acsc-2015-0007
• [9] H. Furmańczyk and M. Kubale: Equitable coloring of corona products of cubic graphs is harder than ordinary coloring. Ars Mathematica Contemporanea, 10(2), (2016), 333-347. DOI: 10.26493/1855-3974.687.99b
• [10] H. Furmańczyk and M. Kubale: Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines. Discrete Applied Mathematics, 234 (2018), 210-217. DOI: 10.1016/j.dam.2016.01.036
• [11] H. Furmańczyk and M. Kubale: Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs. Discrete Applied Mathematics, 237 (2018), 116-122. DOI: 10.1016/j.dam.2017.12.002
• [12] H. Furmańczyk, M. Kubale and V. Mkrtchyan: Equitable coloring of corona multi-products of graphs. Discussiones Mathematicae Graph Theory, 37(4), (2017), 1079-1094. DOI: 10.7151/dmgt.1992
• [13] G. de C.M. Gomes, M.R. Guedes and V.F. dos Santos: Structural parametrizations for equitable coloring. In Latin American Symposium on Theoretical Informatics, Springer, Cham, (2021), 129-140. DOI: 10.1007/978-3-030-61792-9_11
• [14] G. de C.M. Gomes, C.V.G.C. Lima and V.F. dos Santos: Parameterized complexity of equitable coloring. Discrete Mathatematics and Theoretical Computer Scicience, 21(1), ICGT (2018), DOI: 10.48550/arXiv.1810.13036
• [15] A. Hajnal and E. Szemeredi: Proof of a conjecture of Erdös. In Combinatorial Theory and Its Applications, II, Colloquia Mathematica Societatis János János Bolyai, 4 (1970), 601-623. North-Holland, Amsterdam.
• [16] H.A. Kierstead and A.V. Kostochka: Every 4-colorable graph with maximum degree 4 has an equitable 4-coloring. Journal of Graph Theory, 71(1), (2012), 31-48. DOI: 10.1002/jgt.20630
• [17] H.A. Kierstead, A.V. Kostochka, M. Mydlarz and E. Szemerédi: A fast algorithm for equitable coloring. Combinatorica, 30(2), (2010), 217-224. DOI: 10.1007/s00493-010-2483-5
• [18] W.H. Lin and G.J. Chang: Equitable colorings of Cartesian products of graphs. Discrete Applied Mathematics, 160(3), (2012), 239-247. DOI: 10.1016/j.dam.2011.09.020
• [19] W. Meyer: Equitable coloring. The American Mathematical Monthly, 80(8), (1973), 920-922. DOI: 10.1080/00029890.1973.11993408