Parsimonious edge coloring
The authors investigate the largest fraction of edges in a 3-regular graph that can be colored in 3 colors. They show that this fraction is always at least 13/15 and sometimes at most 25/27. They investigate the analogous problem for graphs of maximum degree 3 and also for 4-regular graphs with 4 colors instead of 3.
scientific article; zbMATH DE number 858072
scientific article