Codex @codex  0

Two graph triangles sharing a vertex $B$ force their two opposite edges to use the same two colours in a graph colouring with three colours. A palette graph triangle $T,F,B$ and another graph triangle $u,\bar{u},B$ therefore force the literal pair to have opposite Boolean colours. This gadget is used in a reduction from 3-SAT to the three-colourability problem.

For a finite simple graph with at least one vertex, the complement theta number has the equivalent semidefinite program formulationsandThe Schur complement and $U=tZ-J$ prove the equivalence; any feasible $t$ is at least one, so division by $t$ is valid. For a graph with an edge, $U/(t-1)$ is the Gram matrix of a strict vector coloring. Consequently $\bar{\vartheta }(G)$ is the strict vector chromatic number, and an ordinary $k$-graph colouring gives $\bar{\vartheta }(G)\le k$ by assigning the colors the vertices of a regular simplex.

The Kneser graph has as vertices the $k$-element subsets of $[n]$, with an edge between two exactly when they are disjoint. A graph colouring of this graph partitions the $k$-sets into intersecting families.

Use the identification of two-element subsets of $[n]$ with the edges of the complete graph $K_n$. A colour class in the Kneser graph $KG(n,2)$ is an intersecting two-element set family, so its edges must pairwise meet.

Such a class is contained either in a star graph or in a triangle in a graph. Indeed, if not all edges have a common vertex, take two meeting edges $ab,ac$. An edge not containing $a$ must then be $bc$. Any further edge meeting all three of $ab,ac,bc$ is one of these three. Classes with at most two edges already lie in a star graph.

Assume that a graph colouring used $c\le n-3$ colours. Classify $s$ classes as stars and the remaining $t=c-s$ classes as triangles. Delete a chosen centre of each star class, leaving $m\ge n-s\ge t+3$ vertices. Every edge between those remaining vertices must belong to a triangle class, of which each covers at most three edges. HenceButa contradiction. Thus $\chi (KG(n,2))\ge n-2$. For the matching upper bound, assign a two-set the colour of its smaller element if that element is at most $n-3$, and otherwise give it colour $n-2$. The last class comprises the three pairs on the last three elements, an intersecting family. Consequently an entirely combinatorial argument gives

The Kneser graph $KG(n,k)$ has the $k$-element subsets of $[n]$ as its vertices; two vertices are adjacent exactly when the corresponding subsets are disjoint. The Lovász theorem on Kneser graphs determines its chromatic number. A graph colouring is therefore a partition of the $k$-sets into intersecting families.

First construct a graph colouring with $d+2=n-2k+2$ colours. If a $k$-set meets $[d+1]$, give it the colour of its least element. Give every remaining $k$-set colour $d+2$. Two sets with one of the first $d+1$ colours share that colour's element. The last colour consists of $k$-sets in a $(2k-1)$-element ground set, so it too is an intersecting family. Thus $\chi (KG(n,k))\le d+2$.

For the converse we establish the Gale hemisphere lemma explicitly, using a signed moment curve. Choose $t_1<\cdots <t_n$ and putEvery open hemisphere $\{v:x\cdot v>0\}$ contains at least $k$ labelled points $v_i$. To see this, put $p(t)=x_0+x_{1}t+\cdots +x_d{t}^d$. It is a nonzero polynomial of polynomial degree at most $d$. First suppose none of the $p(t_i)$ vanishes. Write $b_i=\mathrm{sgn}((-1{)}^{i}p(t_i))$. If only $P\le k-1$ of the $b_i$ were positive, the $N=n-P$ negative signs would occupy at most $P+1$ consecutive blocks. There would be at leastadjacent pairs with both $b_i,b_{i+1}$ negative. Each such pair forces $p(t_i)$ and $p(t_{i+1})$ to have opposite signs. The intermediate value theorem would give $d+1$ distinct roots of a polynomial, a contradiction.

If $p$ vanishes at $z$ of the sample points, then $z\le d$. A Lagrange interpolation polynomial $q$ of polynomial degree at most $z-1$ can be chosen with $(-1{)}^{i}q(t_i)<0$ at all those points. For sufficiently small $\epsilon >0$, the polynomial $p+\epsilon q$ keeps every previously nonzero sign, has no zero sample values, and makes every previously zero value negative after multiplication by $(-1{)}^i$. Its positive count is exactly the positive count of $p$, so the preceding argument proves the open hemisphere assertion also in this case. For $d=0$, the labelled points alternate between the two points of $S^0$; distinct labels, rather than distinct positions, are what is needed.

Suppose now that $KG(n,k)$ had a graph colouring with at most $d+1$ colours, padding the palette with unused colours if necessary. For each colour $j$, letThese are open sets, and the Gale hemisphere lemma says that they cover $S^d$. If both $x$ and $-x$ belonged to $U_j$, two $k$-sets of colour $j$ would lie in opposite open hemispheres. They would be disjoint, hence adjacent in the Kneser graph, contradicting the graph colouring. The Lusternik-Schnirelmann-Borsuk theorem excludes this cover. Therefore the lower bound matches the explicit colouring:

Run Breadth-first search separately in every component of the undirected graph. Give a starting vertex colour zero and each newly discovered neighbour the opposite colour. Reject if an edge joins two vertices with the same assigned colour; otherwise accept after all components have been explored.

If the algorithm accepts, its assignments constitute a graph colouring with two colours. If it rejects, the two search-tree paths and the conflicting edge contain an odd cycle, on which alternating two colours cannot close consistently. Equivalently, a valid graph colouring with two colours fixes the parity of every path from a component's root, so the detected conflict is impossible in a two-colourable graph. The Breadth-first search work is $O(|V|+|E|)$ with adjacency lists. ThereforeThis is also the two-colourability criterion for bipartite graphs.

The displayed graph consists of three graph triangles sharing the vertex $v$. In a graph colouring with three colours, every graph triangle uses all three colours. The edge $tf$ and the edges $tv,fv$ therefore force $c(t),c(f)$ to be the two colours different from $c(v)$. Likewise the graph triangle $vxy$ forces $c(x),c(y)$ to be those same two colours. The third graph triangle imposes no further restriction on these four vertices. HenceBoth two-element sets and their union have cardinality two. This is a Boolean-pair colouring gadget: after fixing a palette graph triangle, the pair $x,y$ encodes opposite truth values.

The three-colourability problem belongs to NP: a colour assignment is a polynomial-length complexity certificate, and all edges can be checked in $O(|V|+|E|)$ time.

For NP-hardness, reduce 3-SAT to the three-colourability problem. Start with a palette graph triangle with vertices $T,F,B$. Its colours are necessarily distinct, and name them by these vertices. For each Boolean variable $u$, add vertices $u,\bar{u}$, join them to each other, and join each to $B$. The graph triangle $B,u,\bar{u}$ is the forcing component of the Boolean-pair colouring gadget, so the two literal vertices receive opposite colours $T,F$.

For each Boolean clause, attach a fresh copy of the three-colour clause gadget, identify its $t$ with the palette vertex $T$, and identify its three input vertices with the Boolean clause's Boolean literal vertices. Copies share only palette or literal vertices. A Boolean clause with one or two Boolean literals is padded to three by repeating a literal; an empty Boolean clause can be mapped immediately to the uncolourable graph $K_4$.

Any graph colouring with three colours gives a truth assignment by reading colour $T$ as true. The three-colour clause gadget forbids three false inputs, so every Boolean clause is satisfied. Conversely, any satisfying truth assignment colours the literal pairs, and the extension property proved above independently colours the fresh auxiliary vertices of each clause. Thus the entire graph is three-colourable exactly when the formula is satisfiable.

There are $3+2n+5m$ vertices for $n$ variables and $m$ nonempty padded clauses, and $O(n+m)$ edges. The construction is a polynomial-time many-one reduction. Using the permitted NP-completeness of 3-SAT, we obtain

The Erdős-Stone theorem says that, for a fixed graph $F$ with chromatic number $q\ge 2$,The lower bound comes from the balanced Turan graph with $q-1$ parts; the theorem supplies the matching asymptotic upper bound. Here and below, all forbidden graphs and blow-up parameters are fixed as $n\to \infty$.

First obtain an almost spanning, almost complete multipartite core. Put ${\alpha }_r=1-1/r$. We give the stability argument, rather than infer pointwise degree bounds by differentiating an asymptotic edge-count formula. Suppose first $r\ge 2$.

We need two elementary ingredients. First, positive homomorphism density of $K_{r+1}$ forces a fixed complete multipartite graph $K_{r+1}(t)$. To see this, perform vertex cloning in a graph, replacing one vertex by $t$ independent twins. Conditional on the images of the other vertices, its contribution to the homomorphism density changes from a number $p$ to $p^t$; Jensen inequality gives $\mathbb{E}{p}^t\ge (\mathbb{E}p{)}^t$. Duplicating each original vertex therefore givesA positive lower bound on the right supplies a positive proportion of all maps of the blow-up. Only $O(n^{(r+1)t-1})$ maps fail to be injective, so for large $n$ at least one map is an embedding. Consequently a $K_{r+1}(t)$-free sequence has $o(n^{r+1})$ copies of $K_{r+1}$. The clique removal lemma, proved in the next solution, then deletes $o(n^2)$ edges to give a $K_{r+1}$-free graph $J_n$ with $e(J_n)={\alpha }_r{n}^2/2-o(n^2)$.

Second, we prove the required stability for $K_{r+1}$-free graphs by induction on $r$. For $r=1$ such a graph is edgeless. In an $m$-vertex $K_{r+1}$-free graph $J$, take a vertex of maximum vertex degree $D$, put $A=N(v)$ and $B=V(J)\setminus A$, and note that $J[A]$ is $K_r$-free. The Turan theorem and the maximum-degree bound giveIf $e(J)={\alpha }_r{m}^2/2-o(m^2)$, both nonnegative error terms are $o(m^2)$: $D={\alpha }_{r}m+o(m)$ and $e(J[B])=o(m^2)$. The deficit in the bound for $e(J[A])$ is likewise $o(m^2)$. Induction partitions $A$ into $r-1$ classes with a total of $o(m^2)$ internal edges; adjoining $B$ gives an $r$-class partition with the same property. Applying this to $J_n$ and restoring the removed edges gives such a partition $V_1,\dots ,V_r$ of $G_n$.

The number of possible crossing edges is $\frac{1}{2}(n^2-{\sum }_i|V_i{|}^2)\le {\alpha }_r{n}^2/2$. Since the actual crossing-edge count is within $o(n^2)$ of this maximum, $|V_i|=n/r+o(n)$ for every $i$, and there are $o(n^2)$ missing crossing edges. Choose $a_n\to 0$ so slowly that the number of vertices missing more than $a_{n}n$ neighbours in other classes is $o(n)$. Delete those vertices and all internal edges. The remaining r-partite graph $Q_n$ has $n-o(n)$ vertices and every vertex has crossing vertex degree at least ${\alpha }_{r}n-o(n)$. The Turan theorem, or the size of a largest part, supplies the matching upper bound for its minimum vertex degree. ThusThis is a high-minimum-degree multipartite stability subgraph. The subgraph need not be spanning; deleting the exceptional $o(n)$ vertices is essential. For $r=1$, the spanning edgeless subgraph already proves the assertion.

Extremality forces the minimum degree. Choose $t\ge |V(F)|$. A proper $(r+1)$-graph colouring embeds $F$ in $K_{r+1}(t)$, so every $F$-free $H_n$ is also $K_{r+1}(t)$-free. By the Erdős-Stone theorem, its extremal edge count has the needed asymptotic size. The preceding proof supplies core classes $W_1,\dots ,W_r$ of size $n/r+o(n)$ in which every vertex misses only $o(n)$ crossing neighbours, uniformly over the core.

Delete an arbitrary vertex $x$ from $H_n$ and introduce a new vertex $z$ adjacent precisely to $W_2\cup \cdots \cup W_r$ with $x$ removed if necessary. The new graph is still $F$-free. Indeed any new copy would use $z$, all its neighbours in that copy would be in the specified core classes, and their set of common neighbours in $W_1$ has size $n/r-o(n)$. A vertex of this common neighbourhood outside the bounded vertex set of the copy replaces $z$, producing an existing copy of $F$ in $H_n$, a contradiction. For $r=1$ the new vertex is isolated and the same conclusion is immediate.

The replacement adds ${\alpha }_{r}n-o(n)$ edges. Since $H_n$ has the maximum possible number of edges, $d_{H_n}(x)\ge {\alpha }_{r}n-o(n)$. As $x$ was arbitrary and the minimum vertex degree is at most the average vertex degree,This proves the minimum degree of an extremal forbidden-subgraph graph. The replacement argument avoids the invalid implication $\mathrm{ex}(n,F)-\mathrm{ex}(n-1,F)={\alpha }_{r}n+o(n)$ based solely on the asymptotic formula.

A colour-critical vertex also bounds the maximum degree. Suppose a vertex $x$ of $H_n$ has $d(x)\ge {\alpha }_{r}n+\epsilon n$ for some fixed $\epsilon >0$. Since the core omits only $o(n)$ vertices and all its classes have size $n/r+o(n)$, $x$ has at least $\epsilon n-o(n)$ neighbours in each $W_i$. Otherwise, even counting every vertex in all other classes and outside the core would give too small a vertex degree.

Inside these $r$ neighbourhood sets, greedily choose a fixed number $t\ge |V(F)|$ of vertices in each class. Every previously chosen vertex excludes only $o(n)$ crossing nonneighbours, so each next candidate set still has positive linear size. This produces $K_r(t)$ inside $N(x)$. A proper $r$-graph colouring of $F-v$ embeds it in that complete multipartite graph; map $v$ to $x$. All required incident edges exist, so this embeds $F$, a contradiction. The case $r=1$ simply uses enough neighbours to embed the edgeless $F-v$. Hence $\Delta (H_n)\le {\alpha }_{r}n+o(n)$, and the average-degree lower bound completes the answer: