I am looking for a graph which is maximal triangle-free 3-colorable, but not maximal triangle-free. Here a graph which is maximal triangle-free 3-colorable is a graph where the addition of any edge violates either the triangle-free condition or the 3-colorable condition.

The possible counterexample necessarily has a pair of vertices with distances $\geq 3$ (in fact no two vertices can have distance greater than 3) where every 3-coloring of the graph has those two vertices being the same color. Some stronger things can be proven about the counterexample, such as every neighbor of one of those aforementioned vertices must be connected to a neighbor of the other vertex, and vice versa (otherwise the distance between a vertex and a neighbor of the other is $\geq 3$, so they must be the same color, but this contradicts that the original two vertices are always the same color). If this explanation is unclear I can elaborate more.

It seems if there exists a triangle-free graph which is 3-colorable and two vertices have to be different colors, one could use this to define the desired graph. Another note is that the graph must be at least 11 vertices - adding in the edge between the two vertices results in a triangle-free graph with chromatic number 4, the smallest example of which is the Groetzsch graph.

4more comments