More graph theory

  • Thread starter vshiro
  • Start date

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
 
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 for: More graph theory

Replies
3
Views
20K
  • Posted
Replies
5
Views
2K
  • Posted
Replies
2
Views
1K
  • Posted
Replies
3
Views
1K
  • Posted
Replies
2
Views
2K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top