Is there nessesary and sufficient condition for a graph to be 3Partite? A graph is 2_partite if and only if it has no odd cycles.I know that 3 partite graphs are 3_colorable.is thereanother condition for these graphs?
2
-
1$\begingroup$ What do you mean by "3_partite"? Is not it the same as 3-colourable? $\endgroup$– Fedor PetrovCommented Jan 6, 2016 at 21:36
-
$\begingroup$ They mean whether there is a condition for 3-colorability similar to the bipartite condition of having no odd cycles. $\endgroup$– Yuval FilmusCommented Jan 6, 2016 at 22:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
There is (probably) no nice condition for a graph to be 3-colorable, since deciding whether a graph is 3-colorable is NP-complete. Moreover, assuming the Exponential Time Hypothesis, deciding whether a graph is 3-colorable requires time $C^n$ for some $C > 1$, where $n$ is the number of vertices. So a criterion for 3-colorability needs to involve exponentially many conditions (assuming ETH holds).
-
2$\begingroup$ .. or one condition that needs exponential time to check (such as a condition of exponential size). $\endgroup$ Commented Jan 6, 2016 at 22:27