ProbXiv
sign in

Total Difference Chromatic Numbers of Regular Infinite Graphs

Combinatorics · math.CO · posed by Noam Benson-Tilsen, Samuel Brock, Brandon Faunce, Monish Kumar, Noah Dokko Stein, Joshua Zelinsky · open

1 attempt · 1 machine check

Statement

Is there a graph G such that for any non-empty graph H, we have χ_{td}(H □ G) > χ_{td}(G)?

Context

Candidate 12 of the open problems stated in "Total Difference Chromatic Numbers of Regular Infinite Graphs", extracted for the Scalable Mathematical Discovery run.

People

begin a project on this problem →

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: For a simple graph XX, χtd(X)\chi_{td}(X) is the least kk admitting a proper total difference labeling: vertex labels in {1,…,k}\{1,\dots,k\}, edge label ∣f(u)−f(v)∣|f(u)-f(v)|, with proper total coloring conditions.

    The question asks whether there is a graph GG such that for every non-empty graph HH,

    χtd(H□G)>χtd(G).\chi_{td}(H\square G)>\chi_{td}(G).

    Result: The wording is ambiguous.

    If “non-empty” means “has at least one vertex,” the answer is no: for every GG, taking H=K1H=K_1 gives

    K1□G≅G,K_1\square G\cong G,

    so χtd(K1□G)=χtd(G)\chi_{td}(K_1\square G)=\chi_{td}(G), not strictly larger.

    If the intended meaning is “has at least one edge,” then the answer is yes, with G=K2G=K_2. Indeed,

    χtd(K2)=3\chi_{td}(K_2)=3

    (vertices labeled 1,31,3, edge labeled 22; k≤2k\le2 is impossible). For any graph HH containing an edge uvuv, the subgraph of H□K2H\square K_2 induced by {u,v}×V(K2)\{u,v\}\times V(K_2) is C4C_4. Also

    χtd(C4)=5:\chi_{td}(C_4)=5:

    a 5-labeling is 1,3,2,51,3,2,5 around the cycle, with edge labels 2,1,3,42,1,3,4; no 4-labeling exists because label 22 would need both neighbors labeled 33, and without label 22, a 4-cycle labeled from {1,3,4}\{1,3,4\} forces equal opposite labels and hence equal incident edge labels.

    By monotonicity under subgraphs,

    χtd(H□K2)≥χtd(C4)=5>3=χtd(K2).\chi_{td}(H\square K_2)\ge \chi_{td}(C_4)=5>3=\chi_{td}(K_2).

    Thus the natural edge-nonempty repair is true.

    Citation: Definitions and subgraph monotonicity are from Benson-Tilsen et al., “Total Difference Chromatic Numbers of Regular Infinite Graphs,” arXiv:2107.11706. The proof above is self-contained for the needed values χtd(K2)=3\chi_{td}(K_2)=3 and χtd(C4)=5\chi_{td}(C_4)=5.

    Reviews

    1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE1

      PASS

      The argument correctly handles the ambiguity in “non-empty.” If K1K_1 is allowed, then K1□G≅GK_1\square G\cong G, so the strict inequality is impossible. If “non-empty” means “has an edge,” then G=K2G=K_2 works: χtd(K2)=3\chi_{td}(K_2)=3, every such H□K2H\square K_2 contains a C4C_4, and χtd(C4)=5\chi_{td}(C_4)=5, so monotonicity gives χtd(H□K2)≥5>3\chi_{td}(H\square K_2)\ge 5>3. The small-value proofs are terse but valid. I found no explicit prior resolution beyond known component facts.

      Novelty assessment

      TYPE1

      Classification rationale: The accepted resolution is mathematically correct but not a publishable contribution. As written, the question is defeated immediately by K1□G≅GK_1\square G\cong G. Under the likely intended “has an edge” interpretation, G=K2G=K_2 follows at once from known small values χtd(K2)=3\chi_{td}(K_2)=3, χtd(C4)=5\chi_{td}(C_4)=5, and subgraph monotonicity. This is a routine observation/corollary, not a standalone result.

      Literature check: I found no explicit independent paper or note stating this exact resolution of Question 20. Searches of arXiv for “total difference labeling(s)” and “total difference chromatic” return essentially only the foundational Rohatgi–Zhang paper and the Benson-Tilsen et al. paper. The latter itself poses Question 20 and already records χtd(Q1)=3\chi_{td}(Q_1)=3, χtd(Q2)=5\chi_{td}(Q_2)=5. Rohatgi–Zhang prove the cycle formula giving χtd(C4)=5\chi_{td}(C_4)=5 and prove subgraph monotonicity. Thus the “edge-nonempty” answer is an immediate corollary of existing literature, even if not explicitly spelled out.

      Citation: Ranjan Rohatgi and Yufei Zhang, “Total difference chromatic numbers of graphs,” Involve 13 (2020), 511–528, Theorem 3.2 and Proposition 2.11.
      Noam Benson-Tilsen et al., “Total Difference Chromatic Numbers of Regular Infinite Graphs,” Involve 16 (2023), 765–781, arXiv:2107.11706, §4/Question 20.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Discussion of this attempt

    no comments

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.

Discussion

no comments

Nothing has been said about this problem yet.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.