we-solve (beta)

Math-1104 · mathematics · Graph theory

Bounding the chromatic number of triangle-free graphs with fixed maximum degree

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

A finite simple undirected graph $G=(V,E)$ is triangle-free if no three vertices are pairwise adjacent. Its maximum degree is $\Delta(G)=\max_{v\in V}|\{u:uv\in E\}|$. A proper $q$-colouring is a map $c:V\to\{1,\ldots,q\}$ with different values on adjacent vertices, and $\chi(G)$ is the least possible $q$. For the empty graph set $\chi(G)=\Delta(G)=0$.

The precise inequality displayed in this catalogue record is the following: for every finite triangle-free simple graph, \[ \chi(G)\le\left\lceil\frac{\Delta(G)}2\right\rceil+2. \] The ceiling is the least integer greater than or equal to its argument. Equivalently, for every integer $D\ge0$, every triangle-free graph of maximum degree at most $D$ should admit a proper colouring with $\lceil D/2\rceil+2$ colours. The colour bound is independent of the number of vertices and does not assume regularity or connectedness.

There is a formulation issue worth making explicit. The source discussion relates this to Reed's bound involving clique number, whose triangle-free specialization gives the stronger $\lfloor\Delta/2\rfloor+2$ bound. The present definition preserves the displayed ceiling version; for odd $\Delta$ the two targets differ by one colour. For example, at $\Delta=6$ the displayed question asks for five colours, while at $\Delta=7$ it asks for six. Triangle-free excludes only cycles of length three, so cycles of length four and longer remain permitted.

Short English statement

Can every triangle-free graph be properly coloured with at most half its maximum degree, rounded up, plus two colours?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Math-1104-A2 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-1104

Correspondence coloring with a forbidden clique: Triangle-free graphs are K_4-free, so for sufficiently large maximum degree the correspondence bound implies ordinary chi<=C_4 Delta/log Delta and hence the stated Delta/2+2 bound. Small and moderate maximum degrees are not covered.

This page records partial support. Complete resolution of the catalogue question is not established by this record.

Bounding the chromatic number of triangle-free graphs with fixed maximum degree

OpenAI's claim

Correspondence coloring with a forbidden clique: For each fixed $r\ge4$, the paper claims correspondence chromatic number $O_r(\Delta/\log\Delta)$ in graphs with no $K_r$ subgraph and large maximum degree. Ordinary and list-coloring versions follow, and fixed forbidden subgraphs are also covered.

Mathematical statement of the claimed result

Mathematical claim 1.
For every fixed integer $r\ge4$ there are $C_r>0,\Delta_r\ge3$ with the following implication for a finite simple undirected graph $G$, writing $\Delta=\Delta(G)$: if $\Delta\ge\Delta_r$ and no $K_r$ occurs, then \[\chi_{\mathrm{DP}}(G)\le\left\lceil C_r\frac\Delta{\log\Delta}\right\rceil.\] The DP, or correspondence, chromatic number permits a matching of forbidden color pairs across each edge rather than identical color names. The stated corollary replaces $K_r$-freeness by noninduced $F$-freeness for any fixed finite graph $F$, with constants depending on $F$. It does not prescribe the optimal leading constant or strong edge-coloring bounds.

Outline of the argument

Correspondence coloring with a forbidden clique: Random partial-coloring rounds act directly on the graph of available list entries and forbidden matching pairs. Weights track total list supply, individual probabilities, and conflicting edge mass. An entropy-and-mass potential pays for losses when neighboring vertices are colored, including local adjustments for triangles, until the residual lists can be completed.

Formal verification

Family 184 describes Lean coverage for a large independent set in a fixed-clique-free graph at the logarithmically improved scale; correspondence coloring is separate.

Correspondence coloring with a forbidden clique: No manuscript-specific Comparator is listed in the pinned inventory.

The documented selection does not cover the entire manuscript assertion relevant here.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →

Math-1104-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-1104

Bounding the chromatic number of triangle-free graphs with fixed maximum degree

Definitions and mathematical statement

A finite simple undirected graph $G=(V,E)$ is triangle-free if no three vertices are pairwise adjacent. Its maximum degree is $\Delta(G)=\max_{v\in V}|\{u:uv\in E\}|$. A proper $q$-colouring is a map $c:V\to\{1,\ldots,q\}$ with different values on adjacent vertices, and $\chi(G)$ is the least possible $q$. For the empty graph set $\chi(G)=\Delta(G)=0$.

The precise inequality displayed in this catalogue record is the following: for every finite triangle-free simple graph, \[ \chi(G)\le\left\lceil\frac{\Delta(G)}2\right\rceil+2. \] The ceiling is the least integer greater than or equal to its argument. Equivalently, for every integer $D\ge0$, every triangle-free graph of maximum degree at most $D$ should admit a proper colouring with $\lceil D/2\rceil+2$ colours. The colour bound is independent of the number of vertices and does not assume regularity or connectedness.

There is a formulation issue worth making explicit. The source discussion relates this to Reed's bound involving clique number, whose triangle-free specialization gives the stronger $\lfloor\Delta/2\rfloor+2$ bound. The present definition preserves the displayed ceiling version; for odd $\Delta$ the two targets differ by one colour. For example, at $\Delta=6$ the displayed question asks for five colours, while at $\Delta=7$ it asks for six. Triangle-free excludes only cycles of length three, so cycles of length four and longer remain permitted.

Short English statement

Can every triangle-free graph be properly coloured with at most half its maximum degree, rounded up, plus two colours?

Research attempt

Scope and process.
This is a GPT-6 Astra Ultra research attempt dated 2 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.
Literature and the exact rounding convention.
Kang and Rosenfeld [R1] prove the stronger bound $\chi(G)\le\lceil(\Delta+1)/2\rceil+1$ for triangle-free graphs with $\Delta\ge524$. For even $\Delta$ this equals the catalogue bound; for odd $\Delta$ it saves one additional colour. Thus the large-degree range is already covered by that external theorem. We do not reprove it. The independent work here gives a critical-graph restriction and verifies an infinite family with unbounded chromatic number, making explicit why triangle-freeness alone cannot reduce the question to two-colouring. All graphs and colourings below are ordinary, not list-coloured.
An elementary counterexample reduction.
The greedy bound $\chi\le\Delta+1$ settles $0\le\Delta\le3$, including the empty graph separately. If the displayed target fails, choose a counterexample with the fewest vertices and put $q=\lceil\Delta(G)/2\rceil+2$. Every graph obtained by deleting one vertex satisfies the proposed inequality and hence is $q$-colourable, since its maximum degree cannot increase. If a vertex $v$ had fewer than $q$ neighbours, a $q$-colouring of $G-v$ could be extended to $v$ by an unused colour. Therefore every such minimal counterexample satisfies \[ \delta(G)\ge\lceil\Delta(G)/2\rceil+2. \] It is also connected: if every component satisfied its own bound, reusing one common palette across components would colour $G$ within its bound. Combined with [R1], this confines the missing degree range to $4\le\Delta\le523$. This is a finite range of degrees, not a finite collection of graphs: the order remains unbounded.
A fully analysed family with arbitrarily many colours.
For a graph $H$ with vertices $v_1,\ldots,v_n$, construct $M(H)$ by retaining $H$, adding independent shadow vertices $u_1,\ldots,u_n$, joining $u_i$ to every original neighbour of $v_i$, and adding a vertex $w$ adjacent to every shadow. If $H$ is triangle-free, so is $M(H)$. A triangle through $w$ would require an edge between shadows. A triangle through exactly one shadow $u_i$ and two original vertices would give a triangle through $v_i$ in $H$. There is no triangle through two shadows, and original triangles were excluded.

If $\chi(H)=k$, colour $v_i$ and $u_i$ alike in a $k$-colouring of $H$, then give $w$ a new colour. Thus $\chi(M(H))\le k+1$. For the reverse inequality, suppose $M(H)$ has a $k$-colouring and call the colour of $w$ colour $k$. No shadow has that colour. Recolour every original vertex of colour $k$ with the colour of its shadow. Two adjacent original vertices were not both colour $k$, and a recoloured $v_i$ cannot conflict with an unchanged neighbour $v_j$, because $u_i$ is adjacent to $v_j$. This gives a proper $(k-1)$-colouring of $H$, a contradiction. Hence $\chi(M(H))=\chi(H)+1$.

Start with $H_0=C_5$ and set $H_{t+1}=M(H_t)$. Direct degree counting gives \[ |V(H_t)|=6\cdot2^t-1,\qquad \chi(H_t)=t+3, \qquad \Delta(H_t)=3\cdot2^t-1\quad(t\ge1). \] Indeed original degrees double, shadow degrees become $d_H(v)+1$, and the apex has degree $|V(H)|$; these give the asserted recurrence and its base case. For $t\ge1$, the catalogue bound becomes $3\cdot2^{t-1}+2$, which is at least $t+3$ by elementary induction. Thus every member satisfies the target, despite unbounded chromatic number. The construction tests the interaction of degree and chromatic number; it is not an extremal family for the proposed linear bound.

Verification and remaining obstruction.
The companion script scripts/check_attempt_batch03_colouring_2026_10_02.py constructs the first four members, checks their orders, degrees and absence of triangles, and checks the inductively supplied colourings. The chromatic lower bound is the proof above, not a numerical search. A minimal-counterexample reduction controls local degrees but supplies no recolouring move when every vertex sees all $q$ colours. The Mycielski argument also shows that avoiding triangles does not prevent global colouring obstructions.
Final status.
UNRESOLVED by this attempt. The cited theorem settles large degrees, and the independent restrictions and infinite family are verified. A uniform argument for the remaining finite degree range, with arbitrarily large order and the exact ceiling convention, is missing.

Sources

Go to contribution →