Restrained star edge coloring of graphs and its application in optimal & safe storage practices

W. Evangeline Lydia, J. Vijaya Xavier Parthipan


In this paper we introduce the concept of restrained star edge coloring of graphs by restraining the conditions of the star coloring of graphs. The restrained star edge coloring of graphs is a path based graph coloring which is said to be proper if all the bichromatic subgraphs of the graph are in the form of a galaxy. The minimum requirement for this coloring is its restrained star chromatic index, denoted as χ'rs. This paper exclusively explains, the restrained star edge coloring of several families of graphs including path, cycle, wheel, etc., and provides the exact value of its respective restrained star chromatic index, χ'rs with the usage of appropriate illustrations. In addition to this, an application of this coloring in the optimal utilization of storage spaces and in ensuring safe storage practices is also briefly elaborated.


Graph coloring; Path coloring; Star edge coloring; Restrained star edge coloring; Restrained Star Chromatic Index

Full Text:



M. O. Albertson, G. G. Chappell, H. A. Kierstead, A. Kündgen, and R. Ramamurthi. Coloring with no 2-colored p4’s. the electronic journal of combinatorics, pages R26–R26, 2004.

L. Bezegová, B. Lužar, M. Mockovčiaková, R. Soták, and R. Škrekovski. Star edge coloring of some classes of graphs. Journal of Graph Theory, 81(1):73–82, 2016.

C. Brause, P. Golovach, B. Martin, P. Ochem, D. Paulusma, and S. Smith. Acyclic, star, and injective colouring: bounding the diameter. The Electronic Journal of Combinatorics, pages P2–43, 2022.

C. J. Casselgren, J. B. Granholm, and A. Raspaud. On star edge colorings of bipartite and subcubic graphs. Discrete Applied Mathematics, 298:21–33, 2021.

G. Chartrand and P. Zhang. Chromatic graph theory. CRC press, 2019.

K. Deng. Star edge-coloring of Graphs. PhD thesis, Northwest Normal University, 2007.

W. Evangeline Lydia and J. Vijaya Xavier Parthipan. Star chromatic number and star chromatic index of some cycle related graphs. Research and Reflections on Education, 20(3A):26–32, 2022.

W. Evangeline Lydia and J. Vijaya Xavier Parthipan. Restrained star edge coloring of some wheel related graphs. Conference Proceedings: National Conference on Advances in graph theory, pages 22–29, 2023.

G. Fertin, A. Raspaud, and B. Reed. Star coloring of graphs. Journal of graph theory, 47(3):163–182, 2004.

J. A. Gallian. A dynamic survey of graph labeling. Electronic Journal of combinatorics, 1(DynamicSurveys):DS6, 2022.

B. Grünbaum. Acyclic colorings of planar graphs. Israel journal of mathematics, 14(4):390–408, 1973.

H. Lei and Y. Shi. A survey on star edge-coloring of graphs. arXiv preprint arXiv:2009.08017, 2020.

Y. Wang, Y. Wang, and W. Wang. Star edge-coloring of graphs with maximum degree four. Applied Mathematics and Computation, 340:268–275, 2019.



  • There are currently no refbacks.

Copyright (c) 2023 Evangeline Lydia. W, Vijaya Xavier Parthipan. J

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Ratio Mathematica - Journal of Mathematics, Statistics, and Applications. ISSN 1592-7415; e-ISSN 2282-8214.