Strong edge colorings via flag algebras

A strong edge coloring of a graph is an edge-coloring such that each color class forms an induced matching in G. In 1985, Erdos and Nesetril conjectured that every graph with maximum degree D admits a strong edge coloring using at most 1.25*D^2 colors. If true, it is well-known that this bound would be best possible.

After a series of partial results dating back to a result of Molloy and Reed from 1997, de Joannis de Verclos, Hurley and Kang proved that every graph admits a strong edge coloring using at most 1.772*D^2 colors. In this talk, we describe an adaptation of the flag algebra framework to this setting which yields an improvement to 1.73*D^2.

This is a joint work with Rémi de Joannis de Verclos, Eoin Davey, Eoin Hurley and Ross Kang.