Geodesic
A~reduction of proposittional tautologihood to graph-coloring in three colors
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VI, Tome 40 (1974), pp. 10-13

Voir la notice de l'article provenant de la source Math-Net.Ru

Given a disjunctive normal form $A$ of the length $l$ graph $\Gamma_A$ is constructed such that the number of $\Gamma_A$ is $c\cdot l$ and $\Gamma_A$ has a coloring of vert exes in three colors if and only if $A$ is not a tautology. 
@article{ZNSL_1974_40_a2,
     author = {G. V. Davydov and P. Yu. Suvorov},
     title = {A~reduction of proposittional tautologihood to graph-coloring in three colors},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {10--13},
     publisher = {mathdoc},
     volume = {40},
     year = {1974},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_1974_40_a2/}
}
TY  - JOUR
AU  - G. V. Davydov
AU  - P. Yu. Suvorov
TI  - A~reduction of proposittional tautologihood to graph-coloring in three colors
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 1974
SP  - 10
EP  - 13
VL  - 40
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_1974_40_a2/
LA  - ru
ID  - ZNSL_1974_40_a2
ER  - 
%0 Journal Article
%A G. V. Davydov
%A P. Yu. Suvorov
%T A~reduction of proposittional tautologihood to graph-coloring in three colors
%J Zapiski Nauchnykh Seminarov POMI
%D 1974
%P 10-13
%V 40
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_1974_40_a2/
%G ru
%F ZNSL_1974_40_a2
G. V. Davydov; P. Yu. Suvorov. A~reduction of proposittional tautologihood to graph-coloring in three colors. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VI, Tome 40 (1974), pp. 10-13. http://geodesic.mathdoc.fr/item/ZNSL_1974_40_a2/