An upper bound on the extremal version of Hajnal's triangle-free game

DOI10.1016/J.DAM.2015.06.031zbMATH Open1326.05091arXiv1409.8141OpenAlexW1882048990MaRDI QIDQ897581FDOQ897581

Authors: Csaba Biró, David Jacob Wildstrom, Paul Horn 

Publication date: 7 December 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A game starts with the empty graph on $n$ vertices, and two player alternate adding edges to the graph. Only moves which do not create a triangle are valid. The game ends when a maximal triangle-free graph is reached. The goal of one player is to end the game as soon as possible, while the other player is trying to prolong the game. With optimal play, the length of the game (number of edges played) is called the $K_3$ game saturation number. In this paper we prove an upper bound for this number.

Full work available at URL: https://arxiv.org/abs/1409.8141

Recommendations

• scientific article; zbMATH DE number 140096
• On Hajnal's triangle-free game
• The Game Saturation Number of a Graph
• On saturation games
• Bounded degree, triangle avoidance graph games

zbMATH Keywords

triangle-free graphgame saturationHajnal game

Mathematics Subject Classification ID

2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Domination game and an imagination strategy
• The triangle-free process
• A bound for the game chromatic number of graphs
• Game matching number of graphs
• Toppling numbers of complete and random graphs
• Title not available (Why is that?)
• The Game Saturation Number of a Graph
• On Hajnal's triangle-free game
• The first player wins the one-colour triangle avoidance game on 16 vertices
• A note on the one-colour avoidance game on graphs
• Title not available (Why is that?)

Cited In (12)

• \(\mathcal{F}\)-saturation games
• The constructor-blocker game
• Upper bounds on positional Paris-Harrington games
• Title not available (Why is that?)
• Bounded degree, triangle avoidance graph games
• Linear bounds for cycle-free saturation games
• Saturation games for odd cycles
• On saturation games
• On Hajnal's triangle-free game
• Path Saturation Game on Six Vertices
• The Game Saturation Number of a Graph
• The \(P_5\)-saturation game

This page was built for publication: An upper bound on the extremal version of Hajnal's triangle-free game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897581)