**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:**