An Upper bound for star chromatic index of simple connected sub-cubic graphs

Abstract

This study explores the star chromatic index χ′st(G) of any simple connected sub-cubic graph G, which is a significant parameter in graph theory that measures the minimum number of colours needed to colour the edges of a graph such that no path or cycle of length 4 is bi- coloured. The idea of star edge colouring was introduced by Liu and Deng in 2008, motivated by its vertex version, and since then, it has been studied extensively by many authors. Computing the star chromatic index for a graph can be a challenging problem, and finding an algorithm for it is an active area of research in graph theory. Numerous studies have been conducted introducing upper bounds for the star chromatic index, and the best known upper bound is 7. The primary objective of this study is to establish a better upper bound for the star chromatic index of simple connected sub-cubic graphs, partially answering to the conjecture posed by Dvorak et al. in 2013. The method of colouring introduced in this study is based on categorizing any simple connected sub-cubic graph with respect to its connectivity. Subsequently, it is decomposed into a matching (possibly with paths of length 2) and a collection of disjoint paths and cycles such that every vertex is contained in some path or cycle in the collection. Showing χ′st(G) = 6 for the 3-regular graph of 10 vertices, where all the non-adjacent edges in the matching and in the collection are at a distance 2 from each other was a major result, and it was extended to prove that χ′st(G) ≤ 6 for any simple connected sub-cubic graph.