List $3$-coloring $C_4$-free graphs of diameter-$2$ in polynomial-time
2026-06-29 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors studied a specific kind of graph called a C4-free graph with diameter 2, focusing on whether these graphs can be colored using only three colors without adjacent nodes sharing a color. They developed a method to decide this coloring efficiently in polynomial time. Their work also showed that if such graphs have no universal vertices and have a high maximum degree (at least 17), then these graphs cannot be colored with just three colors. This helps better understand which graphs are easy or hard to 3-color under these conditions.
C4-free graphdiameter3-coloringlist coloringuniversal vertexmaximum degreepolynomial-time algorithmgraph coloring
Authors
Yukihiro Murakami
Abstract
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.