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:
References:
[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.
Keywords: