2-colouring a graph without a monochromatic maximum clique

2-colouring a graph without a monochromatic maximum clique

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple graph containing at least one edge. A clique is a set of pairwise adjacent vertices, and $\omega(G)$ is the largest size of such a set. A maximum clique has size $\omega(G)$; it is not merely a clique maximal under inclusion. An odd hole is an induced cycle of odd length at least five: its vertices have exactly the cycle edges among them.

The conjecture asks whether every graph $G$ with no odd hole admits a map $c:V\to\{0,1\}$ for which every maximum clique contains vertices of both colours. Equivalently, it asks for a partition $V=X\sqcup Y$ with \[ \omega(G[X])<\omega(G) \quad\text{and}\quad \omega(G[Y])<\omega(G). \] The colouring need not be proper, so edges within one colour class are allowed. The forbidden configuration is specifically a monochromatic clique of the largest size occurring anywhere in $G$.

The edge assumption makes explicit the source's word "non-empty": if $G$ has vertices but no edges, each singleton is a maximum clique and cannot use both colours. With $\omega(G)\ge2$ this degeneracy disappears. When $\omega(G)=2$, the requirement becomes an ordinary proper 2-colouring, but for larger clique number it is weaker. Triangles are allowed by the odd-hole hypothesis, and no prohibition on complements of odd holes is imposed.

Short English statement

Can every odd-hole-free graph with an edge be coloured red and blue so that no largest clique is monochromatic?

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 scope.

This is the Hoàng--McDiarmid two-division question. Chudnovsky and Sivaraman [R1] prove divisibility results for restricted forbidden-induced- subgraph classes, rather than for all odd-hole-free graphs. We prove the target when clique and chromatic numbers agree, establish the clique-number-two case directly, and give an explicit nonperfect family where the required partition still exists. Maximum cliques, not all inclusion-maximal cliques, are the objects being split throughout.

An exact certificate whenever $\chi=\omega$.

Suppose $\chi(G)=\omega(G)=w\ge2$, and fix a proper colouring with $w$ colours. Give all vertices of its first colour the new colour red and give every other vertex blue. A clique of size $w$ uses $w$ distinct colours in the original proper colouring, hence uses every one of them. It therefore contains exactly one red vertex and $w-1$ blue vertices. This proves the desired conclusion whenever $\chi=\omega$, without requiring the stronger assertion that every induced subgraph has that equality.

In particular it applies to perfect graphs, but the hypothesis is not forced merely by excluding odd holes. Complements of odd cycles of length at least seven provide explicit counterexamples to that inference, as analysed below. Thus a proof that simply calls every odd-hole-free graph perfect would use a false premise.

The exact clique-number-two case.

If $\omega(G)=2$, then $G$ has no triangle. If it had an odd cycle, choose one of shortest odd length. Any chord would split it into two smaller cycles, exactly one of them odd, contradicting the choice. The cycle is consequently induced. Its length is at least five because triangles are excluded, contradicting odd-hole-freeness. So $G$ has no odd cycle and is bipartite: colour each connected component by distance parity from a root; an edge within one parity class would produce an odd closed walk and hence an odd cycle. The bipartition splits every maximum clique, which in this case is just an edge. The edge assumption in the canonical statement matters: a singleton clique could not be split this way.

A nonperfect family handled by a different partition.

Let $G$ be the complement of $C_{2m+1}$, with $m\ge3$ and the vertices in cyclic order. An independent set in that cycle has size at most $m$: mapping each selected vertex to its successor gives an equally large disjoint set, so twice the size is at most $2m+1$. Selecting alternate vertices attains $m$. Thus $\omega(G)=m$. Every independent set in $G$ is a clique in the original cycle and has size at most two, so $\chi(G)\ge m+1$. Pairing consecutive cycle vertices and leaving one singleton gives $m+1$ colour classes, proving equality. Hence this graph is not covered by $\chi=\omega$.

It has no odd hole, and in fact no induced cycle of any length at least five. If $\ell$ selected vertices induced such a cycle in $G$, each would have degree $\ell-3$ in the induced subgraph of the original cycle. The original maximum degree is two, forcing $\ell\le5$. At $\ell=5$, all five vertices would have original degree two within the selected set, creating a five-cycle component inside $C_{2m+1}$, which is impossible when $2m+1\ge7$.

Partition the cyclic order into consecutive blocks of lengths $m$ and $m+1$. In the original cycle each block induces a path, whose largest independent set has size respectively $\lceil m/2\rceil$ and $\lceil(m+1)/2\rceil$. Both are at most $m-1$ for $m\ge3$. The corresponding clique numbers in $G$ are therefore less than its maximum $m$. Colouring the two blocks differently proves the target for every graph in this family.

What a full solution would imply.

The odd-hole-free class is hereditary. If the desired two-division were available for every member, induction on clique number would give $\chi(G)\le2^{\omega(G)-1}$ for every nonempty member: the two parts each have smaller clique number, colour them separately, and use disjoint palettes. The base case is an edgeless graph. This deduction highlights the strength of a uniform partition rule; it is not a derivation of that rule from a chromatic bound.

Verification and final status.

The companion script [R2] checks clique numbers and the consecutive-block partitions for complements of odd cycles of orders seven through fifteen. The proofs cover all $m$ and distinguish the two different meanings of maximal and maximum. UNRESOLVED. The missing step is finding a suitable two-division for a general odd-hole-free graph outside the explicitly certified families. No arbitrary proper colouring provides that partition when more than $\omega(G)$ colours are required.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3251 (OPG-56230), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, 2-colouring a graph without a monochromatic maximum clique. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/2_colouring_a_graph_without_a_monochromatic_maximum_clique.

• R1 Maria Chudnovsky and Vaidy Sivaraman, Perfect divisibility and 2-divisibility, primary paper, abstract checked 2 October 2026. https://arxiv.org/abs/1704.06667.
• R2 GPT-6 Astra Ultra, exact batch certificates, 2 October 2026. Repository script scripts/check_attempt_batch03_colouring_2026_10_02.py.