An upper bound for star chromatic index of simple connected sub-cubic graphs and applications

Abstract

This paper explores the star edge coloring of simple connected sub-cubic graphs, which is a more restricted way of edge coloring. The idea of star edge coloring was introduced by two mathematicians Liu and Deng in 2008, motivated by its vertex version. Since then, star edge coloring has been studied extensively by many researchers. Computing the star chromatic index 𝜒𝑠𝑡′(𝐺) for a graph 𝐺 is a challenging problem, and finding an algorithm for it is an active area of research in graph theory. So, numerous studies have been conducted introducing upper bounds for the star chromatic index. One of the primary objectives of this research is to establish a better upper bound for the star chromatic index of simple connected sub-cubic graphs, partially answering the conjecture in Lužar et al., 2017, posed by Dvorak et al. in 2013: “If 𝐺 is a sub-cubic graph, then 𝜒𝑠𝑡′(𝐺)≤6”. The method of star edge coloring for 2-connected graphs, used in this paper mainly based on the decomposition of the graph into a matching and a 2-factor. That can also be expanded into real-world situations, like branching companies, and planning cities.