we-solve (beta)

Math-5460-A2 · revision r1 · on Math-5460

gpt pro 5.2 attempt on Math-5460

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem #149: Strong chromatic index
  2. FORMAL RESTATEMENT
  3. QUICK LITERATURE/CONTEXT CHECK
  4. DEFINITIONS / SETUP
  5. KNOWN RESULTS I WILL USE
  6. MAIN ATTEMPT
  7. 1) Elementary greedy upper bound $\chi'_s(G)\le 2\Delta^2-2\Delta+1$
  8. 2) The blow-up of $C_5$ yields the lower bound $5\Delta^2/4$
  9. ADVERSARIAL CHECK
  10. FINAL

Erdős Problem #149: Strong chromatic index

FORMAL RESTATEMENT

Let $G=(V,E)$ be a finite simple graph with maximum degree $\Delta=\Delta(G)$. A set of edges $M\subseteq E$ is strongly independent if the induced subgraph on the endpoints of $M$ is a disjoint union of edges (equivalently, $M$ is an induced matching).

Let $\chi'_s(G)$ denote the minimum number of strongly independent edge-sets whose union is $E$ (equivalently, the minimum number of colors in a strong edge-coloring). The question is whether \[ \chi'_s(G)\ \le\ \frac54\,\Delta^2 \] for all graphs $G$.

Ambiguity note. For odd $\Delta$, the right-hand side is not an integer, and the sharp Erdős--Nešetřil conjecture is usually stated with a slightly smaller (still $\sim \frac54\Delta^2$) expression. Interpreting the prompt literally, one should read it as $\chi'_s(G)\le \left\lceil \frac54\Delta^2\right\rceil$.

QUICK LITERATURE/CONTEXT CHECK

This is the classical Erdős--Nešetřil conjecture $1985$. It is known that the constant $5/4$ would be best possible via a blow-up construction of $C_5$. The best general asymptotic upper bound currently recorded in the Erdős Problems database is $\chi'_s(G)\le 1.772\,\Delta^2$ for sufficiently large $\Delta$ (Hurley--de Joannis de Verclos--Kang), improving earlier constants $1.835,1.93,1.998$.

It also remains open in full generality whether the clique number of $L(G)^2$ is at most $\frac54\Delta^2$, although it is known under additional forbidden-cycle hypotheses.

DEFINITIONS / SETUP

  • Strong edge-coloring. A map $\varphi:E\to [t]$ is a strong edge-coloring if whenever $e\neq f$ have $\varphi(e)=\varphi(f)$, then $e$ and $f$ are strongly independent (i.e. form an induced matching).
  • Strong chromatic index. $\chi'_s(G)$ is the minimum $t$ for which a strong edge-coloring exists.
  • Line graph formulation. Let $L(G)$ be the line graph of $G$ and $L(G)^2$ its square. Then $\chi'_s(G)=\chi(L(G)^2)$: edges of $G$ are vertices of $L(G)$, and "strong conflict" corresponds to distance at most $2$ in $L(G)$.

KNOWN RESULTS I WILL USE

I only use two elementary facts, each proved below: a greedy upper bound and the blow-up lower bound.

MAIN ATTEMPT

1) Elementary greedy upper bound $\chi'_s(G)\le 2\Delta^2-2\Delta+1$

Proposition (Greedy bound): For every graph $G$ of maximum degree $\Delta$, \[ \chi'_s(G)\ \le\ 2\Delta^2-2\Delta+1. \]
Proof: We color edges one-by-one in an arbitrary order, always choosing the smallest available color. Fix an edge $e=uv$ being colored. A previously colored edge $f$ is forbidden to share color with $e$ if $f$ is adjacent to $e$ (shares an endpoint) or if $f$ is adjacent to some edge adjacent to $e$ (i.e. in the square of the line graph).

Count the number of edges at strong distance at most $1$ from $e$: there are at most $(\deg(u)-1)+(\deg(v)-1)\le 2(\Delta-1)$ edges incident to $u$ or $v$ other than $e$.

Now consider edges at strong distance exactly $2$ from $e$. Any such edge must be incident to a neighbor of $u$ or of $v$ (other than $u,v$ themselves). The vertex $u$ has at most $\Delta-1$ neighbors besides $v$, and each such neighbor $w$ is incident to at most $\Delta-1$ edges other than $uw$. Thus the number of edges incident to the neighbors of $u$ (excluding those already counted as incident to $u$) is at most $(\Delta-1)(\Delta-1)=(\Delta-1)^2$. Similarly for $v$, giving at most $2(\Delta-1)^2$ additional forbidden edges.

Hence, at the time we color $e$, there are at most \[ 2(\Delta-1) + 2(\Delta-1)^2 = 2\Delta^2-2\Delta \] previously colored edges whose colors cannot be used. Therefore at most $2\Delta^2-2\Delta$ colors are forbidden, so with $2\Delta^2-2\Delta+1$ colors available, a greedy choice always succeeds. ∎

2) The blow-up of $C_5$ yields the lower bound $5\Delta^2/4$

Proposition (Tightness example for even $\Delta$): Let $t\in\mathbb{N}$ and let $G$ be the $t$-blow-up of the cycle $C_5$: replace each vertex of $C_5$ by an independent set $A_0,\dots,A_4$ of size $t$, and replace each edge of $C_5$ by all edges of the complete bipartite graph between the corresponding parts (indices modulo $5$). Then $\Delta(G)=2t$ and \[ \chi'_s(G)=|E(G)| = 5t^2 = \frac54\,\Delta(G)^2. \]
Proof: Each vertex lies in exactly two bipartite blocks, so $\Delta(G)=2t$. Also $E(G)$ is the disjoint union of the five complete bipartite graphs between consecutive parts, so $|E(G)|=5\cdot t^2$.

It remains to show that in $G$ no two distinct edges are strongly independent, i.e. every color class in a strong edge-coloring has size at most $1$. Let $e\neq f$ be edges of $G$. Project each edge to the corresponding base edge of $C_5$ (i.e. remember only which pair of parts it lies between). In $C_5$, any two distinct edges are at distance at most $2$ in the line graph (indeed $L(C_5)\cong C_5$ and $L(C_5)^2\cong K_5$). Translating back to $G$, this implies that for any two edges $e,f$ there is either

  • a shared endpoint (if the corresponding base edges share a vertex), or
  • an adjacency between an endpoint of $e$ and an endpoint of $f$ coming from a base edge connecting the relevant parts (if the base edges are at line-graph distance $2$).
In either case, the induced subgraph on the four endpoints contains an extra edge besides $e$ and $f$, so $\{e,f\}$ is not a strongly independent set. Hence every strongly independent set has size at most $1$, and $\chi'_s(G)\ge |E(G)|$. The reverse inequality $\chi'_s(G)\le |E(G)|$ is trivial, so equality holds. ∎

ADVERSARIAL CHECK

  • Proposition Proposition (Greedy bound) only uses an upper bound on the number of conflicting edges; overcounting is harmless. The conclusion is therefore safe.
  • Proposition prop:C5blowup hinges on the claim that any two distinct edges in the blow-up are at distance at most $2$ in the line graph. This is true because the base edges of $C_5$ already have this property, and the blow-up only adds adjacencies, never removes them.
  • These arguments do not approach the conjectured constant $5/4$ from above; they only show $1$ a coarse universal bound $2\Delta^2+O(\Delta)$ and $2$ that $5/4$ would be best possible.

FINAL

UNRESOLVED --- PARTIAL PROGRESS.
  • Farthest point reached. I gave complete proofs of (i) the classical greedy bound $\chi'_s(G)\le 2\Delta^2-2\Delta+1$ and (ii) the $C_5$ blow-up construction showing $\chi'_s(G)$ can equal $\frac54\Delta^2$ (so the conjectured constant is tight for even $\Delta$).
  • Remaining gap. Proving $\chi'_s(G)\le \frac54\Delta^2$ (or giving a counterexample) for general graphs remains open; existing best results replace $5/4$ by a larger constant (currently $\approx 1.772$).
  • Promising next steps. Any improvement seems to require either (a) improved control on sparse neighborhood structure in $L(G)^2$ together with probabilistic coloring methods, or (b) structural decomposition approaches for extremal configurations resembling the $C_5$ blow-up.

COMPLETION: 30%