×

On Hajnal’s triangle-free game. (English) Zbl 0757.90096

The following game, proposed by A. Hajnal, is investigated: From two players who alternatively pick edges of a graph on \(n\) points (starting with an empty graph) the loser is the one who picks an edge which completes a triangle. The main result of the paper is the analysis of a version of the game with the additional rule that the chosen edges must always give a connected subgraph of \(K_ n\). Two other versions are also investigated.

MSC:

91A43 Games involving graphs
05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Erdös, P.: Personal communication.
[2] Füredi, Z., Seress, Á.: Maximal triangle-free graphs with restrictions on the degrees, submitted. · Zbl 0787.05054
[3] Füredi, Z., Reimer, D., Seress, Á.: Hajnal’s triangle-free game and extremal graph problems. · Zbl 0764.05043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.