Use greedy vertex coloring algorithm to prove the upper bound of χ

  • Thread starter Thread starter bremenfallturm
  • Start date Start date
bremenfallturm
Messages
81
Reaction score
13
Homework Statement
Let ##e_i(G)## denote the number of vertices of a graph ##G## whose degree is strictly greater than ##i##. Use the greedy algorithm to show that if ##e_i(G) \le i+1## for some ##i##, then ##\chi(G) \le i+1## (Discrete Mathematics by Biggs, 2nd Ed, Exercise 15.7.3)
Relevant Equations
Definition of "the greedy algorithm". One such definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf (I also added a screenshot of the definition in my post)
Hi!

I am struggling with the exercise I mentioned under "Homework statement".

The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf

Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm:
1756886551546.webp


Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed.
I thought that one approach might be to prove that this property of the greedy algorithm is true, given my constraints: ##|\left\{c(j)|j<i, j \in \text{adj}(i)\right\}| \le i##, because that implies that the no color ##> i+1## will be picked by the greedy algorithm.
However, I can't figure out a way to prove that.
 
Prove $$\int\limits_0^{\sqrt2/4}\frac{1}{\sqrt{x-x^2}}\arcsin\sqrt{\frac{(x-1)\left(x-1+x\sqrt{9-16x}\right)}{1-2x}} \, \mathrm dx = \frac{\pi^2}{8}.$$ Let $$I = \int\limits_0^{\sqrt 2 / 4}\frac{1}{\sqrt{x-x^2}}\arcsin\sqrt{\frac{(x-1)\left(x-1+x\sqrt{9-16x}\right)}{1-2x}} \, \mathrm dx. \tag{1}$$ The representation integral of ##\arcsin## is $$\arcsin u = \int\limits_{0}^{1} \frac{\mathrm dt}{\sqrt{1-t^2}}, \qquad 0 \leqslant u \leqslant 1.$$ Plugging identity above into ##(1)## with ##u...

Similar threads

Back
Top