Skip to main content
4 of 13
added 44 characters in body

Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?

It is well known result proved by Holyer that deciding 3-edge colorability of cubic graphs is $NP$-complete problem.

By Vizing's theorem, all cubic graphs are edge colorable using $\Delta +1$. So, the property of 3-edge colorabilty partitions cubic graphs into two infinite sets. Therefore, the property of 3-edge colorability is an interesting natural property of cubic graphs. Another example is the the $NP$-complete problem of deciding whether a cubic graph $G(V, E)$ has a partitioning of $V$ as $T_1 ∪ T_2$ such that $T_1$ and $T_2$ induce trees of equal size (Deciding whether a cubic graph is Yutsis graph). The preceding two example problems demonstrates what I mean by natural interesting property of cubic graphs.

Another natural interesting property of cubic graphs is the problem of deciding the existence of 2-colorable perfect matching in cubic graphs which was proved to be $NP$-complete by Schaefer in his famous dichotomy theorem of CSP's. The problem is to decide the existence of 2-coloring of the vertices of cubic graph such that every vertex has exactly one neighbor of the same color as itself.

I'm interested in a dichotomy theorem that tells us which natural interesting problems on cubic graphs are polynomial-time decidable and which ones are $NP$-complete.

Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?