The positive minimum degree game on sparse graphs

József Balogh, Andrá Pluháry

Research output: Contribution to journalArticlepeer-review


In this note we investigate a special form of degree games de ned by D. Hefetz, M. Krivelevich, M. Stojaković and T. Szabó [4]. Usually the board of a graph game is the edge set of Kn, the complete graph on n vertices. Maker and Breaker alter-nately claim an edge, and Maker wins if his edges form a subgraph with prescribed properties; here a certain minimum degree. In the special form the board is no longer the whole edge set of Kn, Maker rst selects as few edges of Kn as possible in order to win, and our goal is to compute the necessary size of that board. Solving a question of [4], we show, using the discharging method, that the sharp bound is around 10n=7 for the positive minimum degree game.

Original languageEnglish (US)
JournalElectronic Journal of Combinatorics
StatePublished - 2012

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'The positive minimum degree game on sparse graphs'. Together they form a unique fingerprint.

Cite this