Sign up or sign in

4-cycle-free induced subgraphs of grid graphs

Taiki Aiba <taiba3@gatech.edu>, Georgia Institute of Technology

Coauthors: Ernest Croot

Abstract:

The avoidance of induced forests, or induced acyclic subgraphs, in $d$-dimensional grid graphs, or lattice graphs, has been studied in Alon et al. (2001) and later in Caragiannis et al. (2002), finding upper and lower bounds with respect to the number of vertices in a single dimension $n$ and the dimension $d$. In this work, we study the avoidance of induced $C_4$-free subgraphs, a superset of induced forests, of $2$-dimensional grid graphs $G$ and provide an upper bound on the size of maximal sets $S \subseteq V$ such that the induced subgraph $H_{S}$ of $G$ with vertex set $S$ is $C_4$-free. Additionally, we will show that the number of maximal $C_4$-free induced subgraphs with number of vertices slightly smaller than this upper bound is sufficiently small.

Scheduled for: 2026-03-27 03:20 PM: Contributed Papers Session #1.5

Status: Accepted

Collection: Contributed Papers

Back to collection