More graph theory

  • Thread starter vshiro
  • Start date
  • #1
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
 

Answers and Replies

  • #2
rutwig
44
1
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.
 

Suggested for: More graph theory

Replies
7
Views
1K
  • Last Post
Replies
17
Views
594
Replies
9
Views
132
  • Last Post
Replies
1
Views
288
  • Last Post
Replies
2
Views
305
  • Last Post
Replies
1
Views
391
  • Last Post
Replies
17
Views
2K
Replies
23
Views
451
Top