Restricted Extension of Sparse Partial Edge Colorings of Complete graphs

  • Carl Johan Casselgren
  • Lan Anh Pham


Given a partial edge coloring of a complete graph $K_n$ and lists of allowed colors for the non-colored edges of $K_n$, can we extend the partial edge coloring to a proper edge coloring of $K_n$ using only colors from the lists? We prove that this question has a positive answer in the case when both the partial edge coloring and the color lists satisfy certain sparsity conditions.

Article Number