Regular supergraphs of maximal triangle-free graphs (2002)

Originator(s): Stephan Brandt (Ilmenau)

Conjecture/Question: If G is a maximal triangle-free graph and has minimum degree at least n(G)/3, then G has a regular supergraph obtainable by vertex multiplications [B].

Definitions/Background/motivation: A maximal triangle-free graph is one where the addition of any edge creates a triangle. Vertex multiplication means expanding a vertex into an independent set whose vertices inherit all the neighbors of the original vertex.

An affirmative answer also implies the conjecture that all triangle-free graphs with minimum degree exceeding 1/3 of the number of vertices are 4-colorable, as discussed in [B].

Comments/Partial results:

[B2] Brandt, Stephan A 4-colour problem for dense triangle-free graphs. Cycles and colourings (Stará Lesná, 1999). Discrete Math. 251 (2002), no. 1-3, 33--46.


Back to Index Page Link to Glossary