RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. 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.

UDC: 510.66+519.174


 English version:
Journal of Soviet Mathematics, 1982, 20:4, 2376–2381

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025