More graph theory

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

Answers and Replies

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

Related Threads on More graph theory

  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
5
Views
3K
  • Last Post
3
Replies
60
Views
8K
  • Last Post
3
Replies
59
Views
11K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
13
Views
2K
Top