Home
Scholarly Works
2-Colorings of complete graphs with a small number...
Journal article

2-Colorings of complete graphs with a small number of monochromatic K4 subgraphs

Abstract

Denote by kt(G) the number of cliques of order t in the graph G. Let kt(n)=min {kt(G) + kt(Ḡ): |G| = n}, where Ḡ denotes the complement of G, and |G| denotes the order of G. Let ct(n) = k t(n)/(nt, and let ct = limn→∞ct(n). An old conjecture of Erdős (1962), related to Ramsey's theorem, states that ct = 21−(t2).It was shown false by Thomason (1989) for all t⩾4. We present a class of simply describable Cayley graphs which also show the falsity of Erdős conjecture for t = 4. These graphs were found by a computer search and, although of large orders (210-214), they are rather simple and highly regular. The smallest upper bound for c4 obtained by us is 0.976501 x 132, and is given by the graph on the power set of a 10-element set (and, hence, of order 210) determined by the configuration {1,3,4,7,8,10}. and by the graph on the power set of 11 elements (and, hence, of order 211) determined by the configuration {1,3,4,7,8,10,11}. It is also shown that the ratio of edges to nonedges in a sequence contradicting the conjecture for t = 4 may approach 1, unlike in the sequences of graphs Thomason used in 1989.

Authors

Franek F; Rödl V

Journal

Discrete Mathematics, Vol. 114, No. 1-3, pp. 199–203

Publisher

Elsevier

Publication Date

April 28, 1993

DOI

10.1016/0012-365x(93)90366-2

ISSN

0012-365X

Contact the Experts team