{"id":"arxiv/2610.23965","url":"https://arxiv.org/abs/2610.23965","tags":["cs.DM","math.CO"],"score":0,"title":"Two characterizations of chain partitioned probe graphs","domain":"cs.DM","source":"arxiv","authors":["Van Bang Le"],"reviews":0,"subject":"cs.DM","summary":"Chain graphs are exactly bipartite graphs without induced $2K_2$ (a graph with four vertices and two disjoint edges). A graph $G=(V,E)$ with a given independent set $S\\subseteq V$ (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if $G$ can be extended to a chain graph by adding edges between certain vertices in $S$. %there exists a set $E'\\subseteq\\binom{S}{2}$ such that the graph $G'=(V,E\\cup E')$ is a chain graph. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned probe graphs by…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-11","reactions":{}}