Booth Id:
MATH008
Category:
Mathematics
Year:
2024
Finalist Names:
Luo, Austin (School: Morgantown High School)
Abstract:
This project focuses on Packet Radio Networks (PRN), represented as a graph G = (V,E) with V and E as its vertex and edge sets respectively. The vertices represent the set of stations, and two vertices are joined by an edge if the corresponding stations can hear each other's transmissions. The primary objective is to determine the injective chromatic index of PRNs, a measure that involves assigning frequencies to edges to prevent secondary interference which occurs when stations sharing a frequency with their respective neighbors experience interference. We would like to decrease this to maximize the efficiency of the PRN. This concept, introduced in 2015, presents an optimization problem: determining the minimum number of frequencies required for a given PRN G=(V,E) – the injective chromatic index of G. The challenge lies in the computational complexity of pinpointing the exact injective chromatic indices. In this project, using the coloring extension and the discharging methods, I improve existing upper bounds of injective chromatic indices of sparse graphs with small maximum degrees. Additionally, I extend these improvements to sparse graphs with arbitrary maximum degrees. Notably, I rectify an incomplete proof from prior research, providing a validated proof for the result in question. The findings contribute to advancing our understanding of injective chromatic indices, with potential applications in more efficient channel assignments in Packet Radio Networks.