Can Greedy Coloring on Chordal Graph Complements Be Proven Optimal?

[vshiro]

does anyone have an idea on proving that there is a triangle-free k-chromatic graph for every positive integer k?

or, how to prove that given a simplicial ordering on a chordal graph G, running the greedy coloring algorithm on the reverse order gives the optimal coloring on the complement graph?

one might think to use induction but it's all very messy and ecchhh

 

[rutwig]

Usually the proofs in Graph theory have a quite messy appearence. I suggest you to have a look on Harary in order to see how boring it can be. And then I suggest that, if the assertions are true (I have not meditated about it), then try to use the subgraph argument, i.e., try to construct for the arbitrary case a subgraph that contradicts the assumption. See for example the Kuratowski theorem about planarity to see what I mean.