{"id":"arxiv/2608.12848","url":"https://arxiv.org/abs/2608.12848","tags":["math.CO"],"score":0,"title":"Characterizing forbidden induced subgraphs that force top vertices to be Gallai vertices","domain":"math.CO","source":"arxiv","authors":["Yurui Tang"],"reviews":0,"subject":"math.CO","summary":"A vertex of a graph is called a top vertex if it has maximum degree in the graph. A vertex of a graph is called a Gallai vertex if it belongs to every longest path of the graph. Golan and Shan proved that every top vertex of any connected induced-$2P_2$ free graph is a Gallai vertex. Long, Milans, and Munaro subsequently showed that if every connected induced-$H$ free graph has a Gallai vertex, then $H$ must be a linear forest of order at most nine. They also proved that, for every linear forest $H$ of order at most four, every top vertex of any connected induced-$H$ free graph is a Gallai…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-13","reactions":{}}