|
The planar graph 3-colorability (P3C) is one of {bf NP}-complete problem. Duo to probably appearing the second type of mistake in setting colors, a computational algorithm might repeat many times to decide whether it can correct wrong coloring in many examined subgraphs. Then one can turn P3C by means of analyzing some actual graphs (not with theoretically transformation in polynomial time) into the problem of determining whether there is a planar in infinitely many of arbitrary subgraphs. The problem of determining whether an arbitrary graph is a planar is in the class {bf P} and it can be solved with a polynomial time algorithm. But the problem of determining whether there is a planar in arbitrary subgraphs, which have identical order, of $sumlimits_{nu=1}^{L}dbinom{L}{nu}nu!$, or of $sumlimits_{k=1}^{L}sum limits_{nu=1}^{k}dbinom{k}{nu}nu!$, where $L=lceil n/3 rceil-2$ and $n$ is the order of these graphs, isn\ |
|
Keywords:Problems of {bf P} versus {bf NP}, 3-colorable, 3-colorability, computability, computational complexity. |
|