Graphs with coloring redundant edges - Bart Demoen; Phuong-Lan Nguyen (GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB, 2016)
A graph edge is d-coloring redundant if the removal of the edge doesnot change the set of d-colorings of the graph. Graphs that are toosparse or too dense do not have coloring redundant edges. Tight upperand lower bounds on the number of edges in a graph in order for thegraph to have a coloring redundant edge are proven. Two constructionslink the class of graphs with a coloring redundant edge to theK_4-free graphs and to the uniquely colorable graphs. The structureof graphs with a coloring redundant edge is explored.