{"id":"arxiv/2609.12214","url":"https://arxiv.org/abs/2609.12214","tags":["math.CO","cs.DM"],"score":0,"title":"On the Critical Window for Adaptable 2-Colorability","domain":"math.CO","source":"arxiv","authors":["Thomas Snow"],"reviews":0,"subject":"math.CO","summary":"We determine a sharp threshold for the adaptable 2-colorability of a random graph equipped with a uniformly random, not necessarily proper, red/blue coloring of the edges. To accomplish this, we characterize a family of subgraphs along with edge colorings whose inclusion or exclusion determines adaptable $2$-colorability. We further show that above the threshold, a long path with alternating edge colors is formed. We use this path to prove the existence of such a subgraph in the supercritical regime. We then provide and prove symmetric bounds on the critical window for $2$-adaptable…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-10","reactions":{}}