we-solve (beta)

Math-6145-A2 · revision r1 · on Math-6145

gpt pro 5.2 attempt on Math-6145

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: solved. Claims here do not change the source status.

Manuscript

FORMAL RESTATEMENT

All graphs are finite, simple, undirected. A diagonal of a cycle $C=v_0v_1\dots v_{\ell-1}v_0$ means a chord: an edge $v_iv_j$ with $|i-j|\not\equiv 1 \pmod \ell$.

Question $1$: If $G$ is $K_4$-free and $\chi(G)=4$, must $G$ contain an odd cycle with at least two diagonals?

Question $2$: Does there exist a function $f(r)\to\infty$ such that every graph $G$ with $\chi(G)=4$ and with the property that every subgraph on $\le r$ vertices has chromatic number $\le 3$ contains an odd cycle with at least $f(r)$ diagonals?

QUICK LITERATURE/CONTEXT CHECK

I will not use external results beyond what is explicitly stated in the problem text. The text states: the existence of an odd cycle with at least one diagonal is true (Larson), and the first question (two diagonals) was solved affirmatively by Voss. The pentagonal wheel shows that three diagonals are not guaranteed.

ATTACK PLAN

  • Reduce to a minimal counterexample: take a $4$-critical subgraph (every proper subgraph is $3$-colorable). This forces strong structural properties (minimum degree $\ge 3$, 2-connectedness).
  • Use coloring/Kempe-chain arguments on $3$-colorings of $G-e$ (for an edge $e$) to force the existence of specific alternating paths, hence many odd cycles.
  • The missing step is to upgrade "many odd cycles" into one odd cycle that has two chords and to do so under the additional $K_4$-free constraint.

WORK

Lemma 1091.1 (Existence of a $4$-critical subgraph). If a graph $G$ satisfies $\chi(G)=4$, then $G$ has a subgraph $H\subseteq G$ such that $\chi(H)=4$ and every proper subgraph of $H$ has chromatic number at most $3$. Moreover, if $G$ is $K_4$-free, then $H$ is $K_4$-free.

Proof. Among all subgraphs of $G$ with chromatic number $4$, choose one $H$ with the minimum number of vertices; among those, choose one with the minimum number of edges. Then $\chi(H)=4$ by construction. If $H'$ is a proper subgraph of $H$, then either it has fewer vertices (if obtained by deleting a vertex) or the same vertices and fewer edges; in either case, by minimality of $H$, we must have $\chi(H')\le 3$. Thus $H$ is $4$-critical in the standard sense. If $G$ is $K_4$-free, then any subgraph of $G$ is also $K_4$-free, in particular $H$. $\square$

Lemma 1091.2 (Basic properties of $4$-critical graphs). Let $H$ be $4$-critical.

  • (Minimum degree) Every vertex of $H$ has degree at least $3$.
  • (2-connectedness) $H$ has no cut vertex (equivalently, $H$ is 2-connected).

Proof. Minimum degree. Suppose for contradiction that $H$ has a vertex $v$ with $\deg_H(v)\le 2$. By $4$-criticality, $H-v$ is $3$-colorable; fix a proper 3-coloring of $H-v$. The vertex $v$ has at most two neighbors, so among the three colors there is at least one color not used on its neighbors. Assign that color to $v$; this yields a proper 3-coloring of $H$, contradicting $\chi(H)=4$. Hence $\delta(H)\ge 3$.

2-connectedness. Suppose $H$ has a cut vertex $v$. Then $H-v$ has at least two connected components; let $H_1,H_2$ be the induced subgraphs on $v$ together with the vertex sets of two distinct components (so $H=H_1\cup H_2$ and $H_1\cap H_2=\{v\}$). By $4$-criticality, both $H_1$ and $H_2$ are proper subgraphs of $H$, hence each is 3-colorable. Take proper 3-colorings of $H_1$ and $H_2$; by permuting color names in one of them, we may assume $v$ receives the same color in both. Then combining the two colorings gives a proper 3-coloring of all of $H$, contradicting $\chi(H)=4$. Thus $H$ has no cut vertex. $\square$

Lemma 1091.3 (Kempe-chain forcing for a critical edge). Let $H$ be $4$-critical and let $uv\in E(H)$. Then in every proper 3-coloring of $H-uv$, the vertices $u$ and $v$ receive the same color. Moreover, fix such a 3-coloring with colors $\{1,2,3\}$ and suppose $u$ and $v$ have color $1$. Then:

  • $u$ and $v$ lie in the same connected component of the subgraph induced by colors $\{1,2\}$ (a $1$--$2$ Kempe chain).
  • $u$ and $v$ lie in the same connected component of the subgraph induced by colors $\{1,3\}$ (a $1$--$3$ Kempe chain).
In particular, $H$ contains two (not necessarily internally disjoint) $u$--$v$ paths of even length: one alternating colors $1,2$ and one alternating colors $1,3$. Consequently, the edge $uv$ lies on (at least) two odd cycles.

Proof. Because $H$ is $4$-critical, the proper subgraph $H-uv$ is 3-colorable. Let $\varphi$ be a proper 3-coloring of $H-uv$. If $\varphi(u)\neq\varphi(v)$, then $\varphi$ would also be a proper 3-coloring of $H$ (since adding the edge $uv$ would still connect differently colored vertices), contradicting $\chi(H)=4$. Thus necessarily $\varphi(u)=\varphi(v)$.

Now assume $\varphi(u)=\varphi(v)=1$. Consider the induced subgraph $H[\varphi^{-1}(\{1,2\})]$. If $u$ and $v$ lie in different connected components of this induced subgraph, then swapping colors $1$ and $2$ on the component containing $u$ produces another proper 3-coloring of $H-uv$ in which $u$ has color $2$ while $v$ remains color $1$. Then $u$ and $v$ have different colors, and the edge $uv$ can be added without creating a monochromatic edge, giving a proper 3-coloring of $H$, contradiction. Therefore $u$ and $v$ must lie in the same connected component of $H[\varphi^{-1}(\{1,2\})]$. The same argument with colors $1$ and $3$ shows $u$ and $v$ lie in the same component of $H[\varphi^{-1}(\{1,3\})]$.

Any path in the $\{1,2\}$-induced subgraph alternates colors and has even length when both endpoints have color $1$; similarly for the $\{1,3\}$-induced subgraph. Adding the edge $uv$ to either even-length path yields an odd cycle containing $uv$. $\square$

FAST REALITY CHECK (local computation). The pentagonal wheel $W_5$ (5-cycle plus a hub adjacent to all rim vertices) is $K_4$-free and has chromatic number $4$. A brute-force check on this 6-vertex graph found an odd 5-cycle with exactly two diagonals, e.g. cycle $(0,1,2,5,4)$ has chords $(0,5)$ and $(1,5)$.

VERIFICATION

  • Lemmas 1091.1--1091.3 are standard critical-graph facts; I verified each step does not assume planarity or any forbidden subgraph beyond the stated hypotheses.
  • Lemma 1091.3 uses only the Kempe-chain recoloring argument, which is valid for any proper coloring.
  • None of these lemmas by itself forces two chords in a single odd cycle; they only force the existence of many odd cycles through a given edge.

FINAL

UNRESOLVED

(i) Strongest proved partial result. Any $K_4$-free graph $G$ with $\chi(G)=4$ contains a $4$-critical $K_4$-free subgraph $H$ with $\delta(H)\ge 3$ and no cut vertex. For any edge $uv\in E(H)$, $uv$ lies on at least two odd cycles (Lemma 1091.3).

(ii) First gap (crisp). Starting from the forced existence of multiple odd cycles through edges in a $4$-critical $K_4$-free graph, prove that some odd cycle must contain two distinct chords (two diagonals).

(iii) Top 3 next moves.

  • Strengthen Lemma 1091.3 to produce a "theta" subgraph with three internally disjoint $u$--$v$ paths, and analyze when such a theta forces an odd cycle with two chords.
  • Exploit $K_4$-freeness: in the theta configuration, any additional edge between internal vertices of two paths creates either a chorded cycle or a $K_4$; use this to force many chords.
  • For the more general local-to-global question, experiment computationally with known sparse 4-chromatic constructions (e.g. iterated Mycielski graphs) to measure the maximum number of chords forced in odd cycles as a function of local 3-colorability radius.

(iv) Minimal counterexample structure. A minimal counterexample to Question $1$ would be a $4$-critical, $K_4$-free graph $H$ such that every odd cycle of $H$ has at most one chord. Such an $H$ must be 2-connected with minimum degree at least 3 (Lemma 1091.2) and must have the strong Kempe-chain property for each edge (Lemma 1091.3).