Injective Chromatic Index of Packet Radio Networks: Improved Upper Bounds

Overview

This project focuses on Packet Radio Networks (PRN), represented as a graph G = (V,E) with Vand Eas 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 gra phs 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 cont ribute to advancing our understanding of injective chromatic indices, with potential applications in more efficient channel assignments in Packet Radio Networks.

Competition history

• JSHS 2024 Category not listed

Resources

• National JSHS abstract book ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.