# Path-width and chromatic number

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$

• It's the other way around - the chromatic number is at most the pathwidth (+ 1). – daniello May 2 '17 at 18:45
• @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 :) – user45212 May 2 '17 at 18:46
• blush. This should cover all you need: ii.uib.no/~pinar/chordal.pdf – daniello May 2 '17 at 19:10