Graphs with coloring redundant edges

Bart Demoen, Phuong-Lan Nguyen


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.


coloring of graphs and hypergraphs, extremal problems

Full Text:




  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats