Feedback game on 3-chromatic Eulerian triangulations of surfaces

DOI10.1016/J.DAM.2023.12.023arXiv2002.10679MaRDI QIDQ6202935FDOQ6202935

Akihiro Higashitani, Naoki Matsumoto, Kazuki Kurimoto

Publication date: 27 February 2024

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

Abstract: In this paper, we study the feedback game on $3$-chromatic Eulerian triangulations of surfaces. We prove that the winner of the game on every $3$-chromatic Eulerian triangulation of a surface all of whose vertices have degree $0$ modulo $4$ is always fixed. Moreover, we also study the case of $3$-chromatic Eulerian triangulations of surfaces which have at least two vertices whose degrees are $2$ modulo $4$, and in particular, we determine the winner of the game on a concrete class of such graphs, called an octahedral path.

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

zbMATH Keywords

Eulerian triangulationfeedback gameoctahedron addition

Mathematics Subject Classification ID

Applications of graph theory (05C90) 2-person games (91A05) Planar graphs; geometric and topological aspects of graph theory (05C10) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Graph Theory
• On the complexity of some two-person perfect-information games
• GO Is Polynomial-Space Hard
• Construction and enumeration of regular maps on the torus
• Inductive definition of two restricted classes of triangulations
• Undirected edge geography
• Even kernels
• Note On 6-regular Graphs On The Klein Bottle

This page was built for publication: Feedback game on \(3\)-chromatic Eulerian triangulations of surfaces

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