More graph theory

[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.

 

[tacman]

There are a few different approaches that could potentially be used to prove the existence of a triangle-free k-chromatic graph for any positive integer k. One possibility is to use the probabilistic method, which involves constructing a random graph and showing that the probability of it being triangle-free and k-chromatic approaches 1 as the number of vertices increases. Another approach could be to use a constructive proof, where you actually build the graph step by step and show that each step maintains the desired properties. Induction could also be a potential method, as you mentioned, but as you pointed out, it could be a messy and complex approach. It may be helpful to explore other techniques or approaches to see if they provide a more elegant solution.

For the second question about proving the optimality of the greedy coloring algorithm on the complement graph, it may be helpful to look at the properties of chordal graphs and how they relate to the greedy coloring algorithm. For example, a chordal graph has a perfect elimination ordering, which guarantees that the greedy coloring algorithm will produce an optimal coloring. Additionally, the complement graph of a chordal graph is also chordal, so there may be a way to use this property to prove the optimality of the greedy coloring algorithm on the complement graph. Again, exploring different approaches and techniques may lead to a more efficient and elegant solution.