Date of Award

4-7-2024

Document Type

Thesis

School

School of Arts, Sciences, Humanities & Education

Programme

Ph.D.-Doctoral of Philosophy

First Advisor

Dr.S.Balaji

Keywords

Graph Theory, Graph Coloring, Edge Coloring, Strong Edge Coloring, Strong Chromatic Index

Abstract

Graph coloring is a major research area in Graph Theory that has a rich collection of research articles contributed by mathematicians across the world. This thesis focuses on a specific type of Graph coloring where the edges of a graph are colored by a principle called strong edge-coloring. There have been numerous research articles published on the least number of colors required to define such a coloring for a given graph G. This least number, χ′s (G), is called as the strong chromatic index of a graph G. Though conjectures stated as early as 1989 remain unsolved, there have been many results proving the conjecture for particular families of graphs. Other significant contributions have established upper bounds for χ′s (G) for specific classes of graphs such as planar graphs, sparse graphs, and some specific bipartite graphs.

A fair share of the articles published in this area of research includes significant applications in the field of wireless sensor networks. In particular, congestion in wireless data transfer and two types of interferences in wireless communication networks can be avoided by modeling and analyzing these networks using graphs. In particular, the problem of assigning interference-free frequencies to a wireless sensor network is equivalent to the problem of coloring the edges of a graph by the principle of strong edge-coloring. Further, the design of a placement delivery array corresponds to the problem of coloring the edges of a bipartite graph by the principle of Strong edge-coloring.

This thesis investigates the minimum number of colors required to color some popular classes of graphs like paths, cycles, and star graphs and their derivatives. This is followed by an analysis of the factors influencing the strong chromatic index of graphs derived from them. A detailed analysis of the strong edge-coloring of graphs derived from cycles and families of graphs related to cycles is included.

In addition, graphs are classified based on the stability of χ′s(G) under graph operations like vertex deletion, edge deletion and subdivision of edges. Further, there is a discussion on how the parameter varies when new graphs are constructed by duplicating graph elements, generating the line graph L(G) of the given graph G, inflating a given graph G and generating graph products from two graphs, G1 and G2.

The algorithmic aspects of the strong edge-coloring problem are also discussed by defining an algorithm that examines if an assignment of colors for the edges of a graph G can represent a placement delivery array pertaining to a wireless network by verifying if the assignment corresponds to the definition of strong edge-coloring. Two algorithms that color the edges of path graphs and cycle graphs in linear time are also discussed.

Download

Share

COinS