New results on edge-coloring and total-coloring of split graphs

A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. A connected graph G is said to be t-admissible if admits a special spanning tree in which the distance between any two adjacent vertices is at most t . Given a graph G , determining the smallest t for which G is t-admissible, i.e., the stretch index of G , denoted by sigma ( G ), is the goal of the t-Admissibility problem. Split graphs are 3-admissible and can be partitioned into three subclasses: split graphs with sigma = 1 , , 2 or 3. In this work we consider such a partition while dealing with the problem of coloring a split graph. Vizing proved that any graph can have its edges colored with triangle or triangle + 1 colors, and thus can be classified as Class 1 or Class 2 , respectively. When both, edges and vertices, are simultaneously colored, it is conjectured that any graph can be colored with triangle + 1 or triangle + 2 colors, and thus can be classified as Type 1 or Type 2 . Both variants are still open for split graphs. In this paper, using the partition of split graphs presented above, we consider the Edge coloring problem and the Total coloring problem for split graphs with sigma = 2. For this class, we characterize Class 2 and Type 2 graphs and we provide polynomial-time algorithms to color any Class 1 or Type 1 graph. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.