Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-05T15:11:59.417Z Has data issue: false hasContentIssue false

Solution of Irving's Ramsey problem

Published online by Cambridge University Press:  18 May 2009

Heiko Harborth
Affiliation:
Technische Universität Braunschweig, D-3300 Braunschweig, West Germany
Heinz-Michael Nitzschke
Affiliation:
Technische Universität Braunschweig, D-3300 Braunschweig, West Germany
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In [1] the following question was posed by R. W. Irving (see also Conjecture 4.10 in [4]): Is there an edge 2-colouring of the complete bipartite graph K13.17 with no monochromatic K3.3? We give a negative answer in this note (Theorem 2). Furthermore we prove Conjecture 4.11 (i) of [4] (Theorem 1), that is, any edge 2-coloured K2n+i,4n-3 contains a monochromatic K2,n with the 2 and n vertices a subset of the 2n +1 and 4n–3 vertices, respectively. Theorem 1 is a consequence of Satz 4 in [3], however, we give a direct proof here.

Type
Research Article
Copyright
Copyright © Glasgow Mathematical Journal Trust 1980

References

REFERENCES

1.Guy, R. K., (Ed.), Sixth British Combinatorial Conference, Unsolved Problems, No. 13 (Typescript 1977).Google Scholar
2.Harary, F., Graph theory, (Addison-Wesley, 1969).CrossRefGoogle Scholar
3.Harborth, H. and Mengersen, I., Ein Extremalproblem für Matrizen aus Nullen und Einsen, J. Reine Angew. Math. 309 (1979), 149155.Google Scholar
4.Irving, R. W., A bipartite Ramsey problem and the Zarankiewicz numbers. Glasgow Math. J. 19 (1978), 1326.Google Scholar