Graphs with Coloring Redundant Edges
2016  //  DOI: 10.5614/ejgta.2016.4.2.9
Bart Demoen, Phuong-Lan Nguyen

Metrik

  • Eye Icon 159 kali dilihat
  • Download Icon 56 downloads
Metrics Icon 159 kali dilihat  //  56 downloads
Abstrak

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 the$K_4$-free graphs and to the uniquely colorable graphs. The structureof graphs with a coloring redundant edge is explored.

Full text
Show more arrow
 

Metrik

  • Eye Icon 159 kali dilihat
  • Download Icon 56 downloads
Metrics Icon 159 kali dilihat  //  56 downloads