CODEWITHSUNDEEP
graph-theorynp
user3070752
user3070752

Reputation: 734

when a given graph is 3-colorable?

I want to use graph 3-colorability to prove a problem is NP-complete But I'm not sure when a given graph is 3-colorable. I think if it doesn't have any node to be connected to all 3 vertices of a triangle in the graph.But i'm not sure. is it correct?

Upvotes: 3

Views: 1296

Answers (1)

user555045
user555045

Reputation: 64904

No. Having a node connected to all three nodes in a triangle (which is just a more complicated way of saying "it has a clique of size 4") is sufficient but not necessary for the graph to not be 3-colorable. Graphs may be not 3-colorable for different reasons than having a clique of size 4.

For example:

not three colorable

It's not 3-colorable. Proof: the 5-cycle around the outside is not 2-colorable, and then you need an extra color for the middle vertex.

Upvotes: 3

Related Questions