Soft Graph Coloring

• Generalize the metric on colorings from proper/non-proper to ..

• Degree of conflict g

  • g = (number of conflicts)/(total number of edges)
    • range is [0,1]: 0 is best, 1 is worst
  • independent of graph size
  • suitable metric for off-line analysis of progress of anytime colorer
    • a random coloring with C colors has an expected score of g=1/C
      • this acts as a baseline for assessing algorithms
  • applicable even in over-constrained scenarios
    • e.g., 3-coloring a 4-colorable graph