Erdős Problem #22 — K4K_4-free graphs with n2/8n^2/8 edges and o(n)o(n) independence number

About 50 years old · traced to

There remains the following problem. Does there exist a G(n,[n2/8])G(n, [n^2/8]) without a K4K_4 and at most o(n)o(n) independent points? (As usual, G(n,m)G(n, m) denotes a graph with nn points and mm edges.) At present we do not see a promising line of attack. The most we could hope for is the following. For every η>0\eta > 0 there exists an ϵ>0\epsilon > 0 such that whenever nn is sufficiently large, some G=G(n,[(n2/8)(1+ϵ)])G = G(n, [(n^2/8)(1 + \epsilon)]) satisfies I(G)<ηnI(G) < \eta n and α(G)<4\alpha(G) < 4.

References

Additional references

B. Bollobás and P. Erdős, On a Ramsey-Turán type problem, J. Combinatorial Theory Ser. B 21 (1976), 166-168.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.