Id: arxiv/2606.30282 Url: https://arxiv.org/abs/2606.30282 Tags: math.CO, cs.DM Score: 0 Title: List $3$-coloring $C_4$-free graphs of diameter-$2$ in polynomial-time Domain: math.CO Source: arxiv Authors: Yukihiro Murakami Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-29 Page: https://delphi.science/r/arxiv/2606.30282 We show that list $3$-coloring a~$C_4$-free graph of diameter-$2$ can be done in polynomial-time. Our algorithm is based on a structural characterization showing that many such graphs are not~$3$-colorable. In particular, we show that~$C_4$-free graphs of diameter-$2$ without universal vertices, where the maximum degree is at least~$17$, are not~$3$-colorable.