Zapiski Nauchnykh Seminarov LOMI
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zap. Nauchn. Sem. POMI:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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.
English version:
Journal of Soviet Mathematics, 1982, Volume 20, Issue 4, Pages 2376–2381
DOI: https://doi.org/10.1007/BF01629450
Bibliographic databases:
UDC: 510.66+519.174
Language: Russian
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
Citation in format AMSBIB
\Bibitem{Suv79}
\by P.~Yu.~Suvorov
\paper Representation of proof s' by coloured graphs and Hadwiger hypothesis
\inbook Studies in constructive mathematics and mathematical logic. Part~VIII
\serial Zap. Nauchn. Sem. LOMI
\yr 1979
\vol 88
\pages 209--217
\publ "Nauka", Leningrad. Otdel.
\publaddr Leningrad
\mathnet{http://mi.mathnet.ru/znsl3115}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=556232}
\zmath{https://zbmath.org/?q=an:0429.05039|0494.05022}
\transl
\jour J. Soviet Math.
\yr 1982
\vol 20
\issue 4
\pages 2376--2381
\crossref{https://doi.org/10.1007/BF01629450}
Linking options:
  • https://www.mathnet.ru/eng/znsl3115
  • https://www.mathnet.ru/eng/znsl/v88/p209
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Statistics & downloads:
    Abstract page:275
    Full-text PDF :88
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024