In other words, can a planar graph without k3 have a chromatic number larger than 3?
Yes, every triangle-free planar graph is 3-colorable. This is known as Grötzsch's theorem.
Sign up using Google
Sign up using Facebook
Sign up using Stack Exchange
1 year ago