How would I prove that the chromatic number of a graph $G$ is smaller than or equal to the path-width of $G$ + 1? or $\chi(G) \leq pw(G) + 1$

  • 1
    $\begingroup$ It's the other way around - the chromatic number is at most the pathwidth (+ 1). $\endgroup$ – daniello May 2 '17 at 18:45
  • $\begingroup$ @daniello is there any proof of this? Update: I have just realized that you're Dr. Daniel Lokshtanov. I'm a huge advocate of your work and contribution to the theoretical computer science community :) $\endgroup$ – user45212 May 2 '17 at 18:46
  • 1
    $\begingroup$ blush. This should cover all you need: ii.uib.no/~pinar/chordal.pdf $\endgroup$ – daniello May 2 '17 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy