Skip to main content
5 of 6
edited tags
user avatar
user avatar

Paul Erdős: Determine or estimate the number of maximal triangle-free graphs on n vertices

Among the collections of the open problems of Paul Erdős on the website of Professor Fan Chung, there is one called "number of triangle-free graphs".

http://www.math.ucsd.edu/~erdosproblems/erdos/newproblems/NumberOfTriangleFreeGraphs.html

Open Problem: Determine or estimate the number of maximal triangle-free graphs on $n$ vertices.

Is any one working on this problem? Any known related results?

Now I am considering about using a "connection game" method to solve this problem: Given a set of $n$ players, each one chooses to connect to other nodes, if any two neighbors of it connect a new edge(which means there would form a triangle), it has to choose delete either edges with those two neighbors. Then the question is how many different topology connections does it have?

Any comments on this method?

user39815