|
Zapiski Nauchnykh Seminarov LOMI, 1979, Volume 88, Pages 209–217
(Mi znsl3115)
|
|
|
|
Representation of proof s' by coloured graphs and Hadwiger hypothesis
P. Yu. Suvorov
Abstract:
Coloured graph is a directed graph with some vertices and ares coloured in some colours.
If $A$ is a set of $k$-vertex coloured graphs and $G$ is a coloured graph then $G$ is said to be $A$-well-coloured if all its $k$-vertex subgraphs belong to $A$.
We describe a construction of a finite set $B_p$ of 3-vertex graphs with ares coloured in some colours and a finite set $C_p$ of 2-vertex graphs with ares and vertices coloured in some colours for a given formula $P$ of the first order predicate calcules such that $\vdash P$ if and only if there exists $B_p$-well-(arc)coloured graph $G$ which does not permit $C_p$-well-colouring of vertices.
Hadwiger hypothesis (HH): if no subgraph of lopp-free graph $G$ is contracted to $n$-vertex complete graph, then vertices of $G$ can be coloured in $(n-1)$ colours in such a way that neighbouring vertices are coloured in distinct colours.
We construct a formula $X$ of the first order predicate calcules such that HH is equivalent
to $\rceil\vdash X$. Thus HH is reduced to the statement.
If all 3-vertex subgraphs of arc-coloured graph $G$ belong to $B_X$ then the vertices of $G$ can be $C_X$-well-coloured.
Here $B_X$ and $C_X$ are concrete finite sets of 3-vertex and 2-vertex coloured graphs.
Citation:
P. Yu. Suvorov, “Representation of proof s' by coloured graphs and Hadwiger hypothesis”, Studies in constructive mathematics and mathematical logic. Part VIII, Zap. Nauchn. Sem. LOMI, 88, "Nauka", Leningrad. Otdel., Leningrad, 1979, 209–217; J. Soviet Math., 20:4 (1982), 2376–2381
Linking options:
https://www.mathnet.ru/eng/znsl3115 https://www.mathnet.ru/eng/znsl/v88/p209
|
Statistics & downloads: |
Abstract page: | 275 | Full-text PDF : | 88 |
|