Coloring Dense Triangle-Free Graphs and Hajós' Conjecture

Definitions and mathematical statement

Let $G$ be a finite simple graph, with $n=|V(G)|\geq1$, minimum degree $\delta(G)$, and chromatic number $\chi(G)$. Triangle-free means that $G$ has no cycle of length three. Define the optimal possibly infinite bound \[ f_{\geq}(1/3)=\sup\{\chi(G):G\text{ is triangle-free},\ |V(G)|=n\geq1,\ 3\delta(G)\geq n\}. \] The first source question is whether $f_{\geq}(1/3)<\infty$, and specifically whether $f_{\geq}(1/3)=4$. An upper bound of four and its optimality are separate requirements in the equality formulation. The source explicitly includes the boundary $3\delta(G)=n$.

The supplied assessment dated 2026-08-21 labels this part solved by the four-color theorem of Brandt--Thomassé. It does not reproduce that theorem's hypotheses. In particular, a statement for $3\delta(G)>n$ alone would not establish the displayed non-strict version; the boundary case must be checked against the cited paper before the assessment is applied to the exact extracted question. This draft preserves the non-strict question rather than replacing its threshold.

The second source question is: Is Hajós' conjecture true for triangle-free graphs? The record does not identify which conjecture bearing this name is intended. Under the chromatic subdivision reading, its statement is \[ \forall G\text{ finite simple and triangle-free},\quad \chi(G)=k\ \Longrightarrow\ G\text{ contains a subdivision of }K_k. \] Here a subdivision replaces each edge by a path, and the replacing paths have pairwise disjoint interiors and no internal branch vertex. If instead the cycle-decomposition conjecture is intended, the question is whether every triangle-free finite simple Eulerian graph on $n$ vertices admits an edge partition into at most $\lfloor(n-1)/2\rfloor$ simple cycles. Eulerian here means that all vertex degrees are even; isolated vertices may be retained. These are distinct conjectures, and neither is selected silently from the unexpanded name. The supplied assessment reports that the intended triangle-free Hajós question remains unresolved, giving the combined record the label partially solved; attribution of that status to either explicit formulation requires source verification.

Short English statement

The first question asks for a uniform chromatic bound, specifically four, at minimum degree at least one third of the order. The second asks about a triangle-free version of Hajós' conjecture, whose intended meaning is not specified. The dated solved/open split needs checks of the degree boundary and the named conjecture.

Sources

• Local UnsolvedMath registry, permanent ID 30000026, catalogue entry, Coloring Dense Triangle-Free Graphs and Hajós' Conjecture.
• Combinatorics (2004), Oberwolfach Reports, pp. 5--110, DOI https://doi.org/10.4171/owr/2004/01; supplied report link https://ems.press/content/serial-article-files/45848.
• Brandt--Thomassé, supplied paper link https://perso.ens-lyon.fr/stephan.thomasse/liste/vega11.pdf. The record supplies no article title or exact theorem statement.
• Reference labeled "SIAM paper": https://doi.org/10.1137/23M157082X. No title or author list is included in the record.
• Supplied literature assessment checked 2026-08-21; it reports the dense coloring part solved and the intended triangle-free Hajós part unresolved.