Equitable Total Coloring of Line Graph of Certain Graphs

Abstract

An equitable total-coloring of a graph G is a proper total-coloring such that the number of vertices and edges in any two color classes differ by at most one. In this paper, we determined the equitable total chromatic number for line graph of ladder, slanting ladder, triangular snake, alternate triangular snake, quadrilateral snake and alternate quadrilateral snake

Introduction: Graph coloring is a fundamental problem in graph theory with applications in scheduling, networking, and resource allocation. A total-coloring of a graph G is an assignment of colors to both vertices and edges such that adjacent vertices, adjacent edges, and incident vertex-edge pairs receive distinct colors. An equitable total-coloring is a special type of total-coloring where the sizes of any two color classes differ by at most one. The equitable total chromatic number, denoted as is the minimum number of colors required for such a coloring.

Objectives: To establish the equitable total chromatic number for the line graph of specific families  of structured graphs. To develop systematic coloring techniques for achieving an equitable total-     coloring of these graphs. To contribute to the broader study of equitable colorings in graph theory and expand the known results in this domain.

Methods: To determine the equitable total chromatic number for the line graphs of the given graph families, we employ the following methodology: Graph Construction: We formally define the structure of the ladder, slanting ladder, triangular snake, alternate triangular snake, quadrilateral snake, and alternate quadrilateral snake, along with their corresponding line graphs. Coloring Strategy: We apply systematic coloring techniques ensuring that adjacent vertices, adjacent edges, and incident vertex-edge pairs receive different colors while maintaining equitable distribution of color classes. Mathematical Analysis: We derive lower bounds for and establish its exact value using combinatorial and structural properties of the graphs. Verification and Proof: We validate the obtained chromatic numbers through case-based analysis and, where applicable, provide rigorous proofs for correctness.

Results: The study successfully determines the exact value of the equitable total chromatic number for the line graphs of the considered structured graphs. The results provide new insights into the equitable total-coloring of line graphs of ladder-based and snake-like structures, which are commonly encountered in chemical graph theory and network design problems.

Conclusions: This paper establishes the equitable total chromatic number for the line graphs of several structured graphs, contributing to the ongoing research in equitable colorings. The findings demonstrate that the structural properties of the base graphs significantly influence their equitable total chromatic numbers. These results can be extended to other classes of graphs, and future research may explore algorithmic approaches for efficient equitable total-coloring in larger and more complex graph families