ProbXiv
sign in

An Extension on Neighbor Sum Distinguishing Total Coloring of Graphs

Combinatorics · math.CO · posed by Jing-zhi Chang, Chao Yang, Zhi-xiang Yin, Bing Yao · open

1 attempt · 1 machine check

Statement

Let Kn1,n2,...,nrK_{n_{1},n_{2},...,n_{r}} be a complete r-partite graph with r vertex sets Xi(i∈[1,r])X_{i}(i \in[1,r]) and ∣Xi∣=ni|X_{i}|=n_{i} , ∑i=1r=n\sum_{i=1}^{r}=n . Besides (i) and (ii) in Theorem 8, fgndi∑(Kn1,n2,...,nr)≤3fgndi_{\sum}(K_{n_{1},n_{2},...,n_{r}})\le 3 ?

Context

Candidate 3 of the open problems stated in "An Extension on Neighbor Sum Distinguishing Total Coloring of 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: Reconstructed statement: For every complete multipartite graph Kn1,…,nrK_{n_1,\dots,n_r} with positive part sizes and not equal to K2K_2, the neighbor full sum distinguishing total chromatic number satisfies

    fgndi⁡∑(Kn1,…,nr)≤3.\operatorname{fgndi}_{\sum}(K_{n_1,\dots,n_r})\le 3.

    Here a total coloring f:V(G)∪E(G)→{1,…,k}f:V(G)\cup E(G)\to\{1,\dots,k\} is NFSD if for every edge xyxy,

    ϕ(x)≠ϕ(y),ϕ(x)=f(x)+∑e∋xf(e)+∑y∈N(x)f(y).\phi(x)\ne \phi(y),\qquad \phi(x)=f(x)+\sum_{e\ni x}f(e)+\sum_{y\in N(x)}f(y).

    Literal caveat: if K1,1=K2K_{1,1}=K_2 is included, the statement is false, since for its only edge uvuv,

    ϕ(u)=f(u)+f(uv)+f(v)=ϕ(v)\phi(u)=f(u)+f(uv)+f(v)=\phi(v)

    for every total coloring. The natural repair, consistent with the paper’s context, is to exclude K2K_2.

    Result: The repaired statement is true.

    Proof. Relabel the parts so that

    n1≥n2≥⋯≥nr.n_1\ge n_2\ge \cdots \ge n_r.

    If r=2r=2, write the graph as Km,nK_{m,n}. If m≠nm\ne n, coloring every vertex and edge by 11 gives weights 2n+12n+1 on the mm-part and 2m+12m+1 on the nn-part, hence distinct. If m=n=t≥2m=n=t\ge2, color all vertices in one part by 11, all vertices in the other by 22, and all edges by 11. Then the two part weights are

    1+t+2t=1+3t,2+t+t=2+2t,1+t+2t=1+3t,\qquad 2+t+t=2+2t,

    which differ since t≥2t\ge2.

    Now assume r≥3r\ge3. Color every vertex by 11. Let

    T={r+1,r odd,r,r even.T=\begin{cases} r+1,& r\text{ odd},\\ r,& r\text{ even}. \end{cases}

    For an edge between XiX_i and XjX_j, assign color

    f(XiXj)={1,i+j<T,2,i+j=T,3,i+j>T.f(X_iX_j)= \begin{cases} 1,& i+j<T,\\ 2,& i+j=T,\\ 3,& i+j>T. \end{cases}

    All vertices in the same part have the same weight

    Φi=1+∑j≠inj(1+f(XiXj)).\Phi_i=1+\sum_{j\ne i} n_j\bigl(1+f(X_iX_j)\bigr).

    We show Φ1<Φ2<⋯<Φr\Phi_1<\Phi_2<\cdots<\Phi_r. For 1≤i<r1\le i<r,

    Φi+1−Φi=(ni−ni+1)(1+f(XiXi+1))+∑j≠i,i+1i+j∈{T−1,T}nj.\Phi_{i+1}-\Phi_i =(n_i-n_{i+1})(1+f(X_iX_{i+1})) +\sum_{\substack{j\ne i,i+1\\ i+j\in\{T-1,T\}}} n_j.

    The first term is nonnegative because ni≥ni+1n_i\ge n_{i+1}. The index set in the sum is nonempty: for odd rr, the candidates are j=r−i,r+1−ij=r-i,r+1-i; for even rr, the candidates are j=r−1−i,r−ij=r-1-i,r-i, and at least one is valid and not equal to ii or i+1i+1. Hence the sum contains a positive njn_j. Therefore Φi+1−Φi>0\Phi_{i+1}-\Phi_i>0.

    Thus adjacent vertices, which always lie in distinct parts, receive distinct weights. This is an NFSD-total 33-coloring, so

    fgndi⁡∑(Kn1,…,nr)≤3.\operatorname{fgndi}_{\sum}(K_{n_1,\dots,n_r})\le3.

    Citation: Problem and definitions: Chang, Yang, Yin, Yao, “An Extension on Neighbor Sum Distinguishing Total Coloring of Graphs,” arXiv:2201.02781. No external resolution is used here.

    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 proposed coloring is valid and proves the desired ≤3\le 3 bound for all complete multipartite graphs except K2K_2, which the paper’s definitions already exclude. The weight-difference formula is correct, and the threshold edge-coloring for r≥3r\ge3 indeed gives strictly ordered part weights. The bipartite cases are also handled. Searches found only the original paper/partial cases, not a prior general resolution.

      Novelty assessment

      TYPE1

      Classification rationale: The result appears genuinely new but very minor. It resolves a narrow leftover case from an arXiv preprint by a short explicit 3-color construction for complete multipartite graphs. The argument is elementary and would not support a standalone standard-journal paper except perhaps as part of a larger note/corrigendum.

      Literature check: I found no source resolving the missing complete multipartite cases for the non-proper parameter fgndi∑fgndi_{\sum}. The original arXiv paper proves only the all-distinct and all-equal part-size cases, then asks Problem 2 for the remaining cases, despite its abstract loosely saying “complete rr-partite graphs.” Searches for the exact terminology and notation, including “neighbor full sum distinguishing total coloring,” “fgndi,” “complete r-partite,” and “complete multipartite,” led only to the original paper and to related papers on the proper-total-coloring variant ftndiΣftndi_{\Sigma} or other graph classes, not this non-proper 3-color bound.

      Citation: Chang, Yang, Yin, Yao, “An Extension on Neighbor Sum Distinguishing Total Coloring of Graphs,” arXiv:2201.02781, Theorem 11 and Problem 2. Related but different proper-coloring line: Yue–Wen, Axioms 2025; Wen–Yue–Li–Lai, Discrete Applied Mathematics 389 (2026), 46–57.

      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.