Problem 15.1: Erdős' Property B


m(4) ≥ 21 was obtained in the ph.d.-thesis
G. Manning, The M(4) problem of Erdős and Hajnal, Ph.D. dissertation, Northern Illinois University 1997.

In 2008 Patric R. J. Östergård announced that by an exhaustive computer search he obtained m(4) > 22, i.e. the upper bound 23 by P.D. Seymour and B. Toft is the correct value.
Patric R. J. Östergård, On the minimum size of 4-uniform multigraphs without property B, private manuscript 2008, 12 pages.
In a private communication Östergård has mentioned as a still unsolved problem if the example of Seymour and Toft is perhaps the unique example showing that m(4) ≤ 23 - no other example is known at present (the independent examples of Seymour and Toft are indeed isomorphic, even if they originally were described in different terms).

August 13, 2010 Tommy R. Jensen and Bjarne Toft


Back to Overview menu
Back to Graph Coloring Problems homepage

Last modified August 2010 Tommy R. Jensen and Bjarne Toft