Graphs with coloring redundant edges
KU Leuven, Belgium, Bart Demoen, Phuong‐Lan Nguyen, UCO, Angers, France · Electronic Journal of Graph Theory and Applications · 2016
A graph edge is $d$-coloring redundant if the removal of the edge does not change the set of $d$-colorings of the graph. Graphs that are too sparse or too dense do not have coloring redundant edges. Tight upper and lower bounds on the number of edges in a graph in order for the graph to have a coloring redundant edge are proven. Two constructions link the class of graphs with a coloring redundant edge to the $K_4$-free graphs and to the uniquely colorable graphs. The structure of graphs with a coloring redundant edge is explored.