Friday, July 2 2021

2:00pm - 3:00pm

2:00pm - 3:00pm

Masters Presentation

Star Chromatic Index of Subcubic Graphs

A star edge coloring of a graph is a proper coloring of the edges such that there are no bicolored cycles of length 4 or paths of length 4. The star chromatic index of a graph $G$, denoted $\chi_s'(G)$, is the smallest number of colors needed to give a star edge coloring of $G$. A subcubic graph is a graph with maximum degree at most 3. Dvořák, Mohar, and ámal (2013) proved that every subcubic graph is 7-star-edge-colorable, and they conjectured that for any subcubic graph, the star chromatic index is at most 6.

In this project, we constructed an integer program to determine if a graph is $k$-star-edge-colorable. We used the integer program to experimentally verify the conjecture for subcubic graphs on at most 19 vertices. As an approach to proving the conjecture for planar subcubic graphs, we created a precoloring extension algorithm and have used this to find reducible configurations for a future discharging proof.

In this project, we constructed an integer program to determine if a graph is $k$-star-edge-colorable. We used the integer program to experimentally verify the conjecture for subcubic graphs on at most 19 vertices. As an approach to proving the conjecture for planar subcubic graphs, we created a precoloring extension algorithm and have used this to find reducible configurations for a future discharging proof.

Speaker: | Rebecca Robinson |

Affiliation: | |

Location: | See email for Zoom link |

Done