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.

  • $\begingroup$ You have repeated maximal triangle free twice, could you clarify? $\endgroup$
    – vidyarthi
    Aug 12 '20 at 6:53
  • $\begingroup$ By maximal triangle-free, I mean a graph which is triangle-free, and the addition of any edge creates a triangle, not maximal in terms of edge count (which are the complete bipartite graphs) $\endgroup$ Aug 12 '20 at 7:15
  • $\begingroup$ From your title you seem to be looking for a graph which is maximal triangle-free, but not maximal triangle-free. Do you maybe mean something else for one of these? $\endgroup$ Aug 12 '20 at 7:30
  • $\begingroup$ The graph should be maximal with respect to both properties - triangle-free and 3-colorable $\endgroup$ Aug 12 '20 at 7:33
  • $\begingroup$ dosent a $5$-cycle do the job? $\endgroup$
    – vidyarthi
    Aug 12 '20 at 8:03

Here's an example of such a graph. If you remove the top vertex, this is just the Grötzsch graph with an edge removed. Since the the Grötzsch graph is minimal with respect to having chromatic number 4, the vertices of the removed edge must be the same color in any 3-coloring. We need this extra vertex at the top to make the graph maximal with respect to being triangle-free and 3-colorable . Since this is not maximal with respect to just being triangle-free, this graph has the property you want. (It's pretty easy to check the above claims, since this graph has a unique 3-coloring up to swapping the colors) 1


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.