Title: Graphs with coloring redundant edges
Authors: Demoen, Bart ×
Nguyen, Phuong-Lan #
Issue Date: 10-Oct-2016
Publisher: Indonesian Combinatorial Society (InaCombS), Institut Teknologi Bandung
Series Title: Electronic Journal of Graph Theory and Applications vol:4 issue:2 pages:223-230
Abstract: 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.
ISSN: 2338-2287
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
demoennguyen.pdf Published 386KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science