List-edge-coloring of cubic graphs

• Grant number: 25/13573-6
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: December 01, 2025
• End date: November 30, 2026
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Candida Nunes da Silva
• Grantee: Camila Yasmin Martins
• Host Institution: Centro de Ciências em Gestão e Tecnologia (CCGT). Universidade Federal de São Carlos (UFSCAR). Campus de Sorocaba. Sorocaba , SP, Brazil

Abstract

A \emph{$k$-edge-coloring} of a graph $G=(V,E)$ is an assignment of colors from the set $\{1, 2, \ldots ,k\}$ to the edges in $E$ such that adjacent edges receive distinct colors. The chromatic index of $G$, denoted by $\chi'(G)$, is the smallest integer $k$ such that $G$ admits a \emph{$k$-edge-coloring}. The concept of \emph{list $k$-edge-coloring} is defined similarly, however, the integer $k$ refers to the size of a list $\ell(e)$ of distinct colors available to color each edge $ e \in E$. The goal is to obtain an edge coloring such that the color assigned to each edge $e$ belongs to $\ell(e)$, and adjacent edges receive distinct colors. The problem of interest is to determine the smallest $k$ such that $G$ admits a \emph{$k$-edge-list-coloring}; this integer is called the \emph{list-chromatic index} of $G$, and is denoted by $\chi'_L(G)$. The concept of $k$-edge-list-coloring is a generalization of $k$-edge-coloring, since when all the lists contain the same set of $k$ colors, the two concepts become equivalent. A well-known open conjecture related to list edge-colorings is the List Edge Coloring Conjecture, which states that $\chi'(G) = \chi'_L(G)$ for every graph $G$. The main classes of graphs for which the conjecture is known to be valid are bipartite graphs and complete graphs with an odd number of vertices. Different techniques have been used: a purely combinatorial one for the first class, and an algebraic approach for the second. We will study these two techniques with the aim of not only understanding them in depth but also of identifying new classes of graphs to which they might be applied in the future. (AU)