3-Coloring $C_4$ or $C_3$-free Diameter Two Graphs

Tereza Klimošová, Vibha Sahlot

The question of whether 3-Coloring can be solved in polynomial-time for the diameter two graphs is a well-known open problem in the area of algorithmic graph theory. We study the p…