{"id":"arxiv/2605.17080","url":"https://arxiv.org/abs/2605.17080","tags":["math.CO"],"score":0,"title":"Structural characterization and efficient recognition of probe diamond-free graphs","domain":"math.CO","source":"arxiv","authors":["Luciano Norberto Grippo Min Chih Lin"],"reviews":0,"subject":"math.CO","summary":"A graph is probe diamond-free if its vertex set admits a partition into probes and nonprobes, where the set of nonprobes is independent, such that adding edges only between pairs of nonprobes yields a diamond-free graph. Although this class admits a characterization by forbidden induced subgraphs, such a characterization does not directly lead to an efficient recognition algorithm. In this work we introduce a new structural characterization of probe diamond-free graphs based on a local condition, called the \\emph{locally union of complete split} property, together with an auxiliary bipartite…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-16","reactions":{}}