ProbXiv
sign in

On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs

Combinatorics · math.CO · posed by Ali Dehghan, Mohsen Mollahajiaghaei · open

1 attempt · 1 machine check

Statement

Is this true “for any graph GG, diss[G]≤χ(G)dis_s[G] \le \chi(G)?”

Context

Candidate 7 of the open problems stated in "On the algorithmic complexity of adjacent vertex closed distinguishing colorings number 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 conjecture: For every finite simple undirected graph GG,

    dis⁡s[G]≤χ(G),\operatorname{dis}_s[G]\le \chi(G),

    where a labeling f:V(G)→S⊂Nf:V(G)\to S\subset \mathbb N is closed distinguishing if, for every edge uvuv with N[u]≠N[v]N[u]\ne N[v],

    ∑x∈N[u]f(x)≠∑x∈N[v]f(x),\sum_{x\in N[u]} f(x)\ne \sum_{x\in N[v]} f(x),

    and dis⁡s[G]\operatorname{dis}_s[G] is the minimum possible number ∣S∣|S| of distinct labels used. Equivalently, in the “strong” color version, adjacent non-closed-twin vertices must have different color-multisets on their closed neighborhoods.

    Result: The conjecture is false.

    Let H=K4H=K_4. Construct GG by replacing every edge ijij of K4K_4, with i<ji<j, by a path

    i−aij−bij−j.i-a_{ij}-b_{ij}-j.

    Thus GG is the graph obtained from K4K_4 by subdividing every edge twice.

    First, χ(G)=3\chi(G)=3. Indeed, color all original vertices of K4K_4 with color 11, all vertices aija_{ij} with color 22, and all vertices bijb_{ij} with color 33. This is a proper 3-coloring. Also, a triangle of K4K_4 becomes a 9-cycle in GG, so GG is not bipartite. Hence χ(G)=3\chi(G)=3.

    Now let ff be any closed distinguishing labeling of GG. For each original edge ijij of K4K_4, consider the middle edge aijbija_{ij}b_{ij}. We have

    N[aij]={i,aij,bij},N[bij]={aij,bij,j}.N[a_{ij}]=\{i,a_{ij},b_{ij}\},\qquad N[b_{ij}]=\{a_{ij},b_{ij},j\}.

    These closed neighborhoods are distinct, so the distinguishing condition gives

    f(i)+f(aij)+f(bij)≠f(aij)+f(bij)+f(j),f(i)+f(a_{ij})+f(b_{ij}) \ne f(a_{ij})+f(b_{ij})+f(j),

    hence f(i)≠f(j)f(i)\ne f(j).

    Therefore the four original vertices of K4K_4 must receive pairwise distinct labels. Thus

    dis⁡s[G]≥4>3=χ(G).\operatorname{dis}_s[G]\ge 4>3=\chi(G).

    So the proposed inequality fails.

    In fact, replacing every edge of KmK_m by a path of length 33 gives 3-chromatic graphs with dis⁡s≥m\operatorname{dis}_s\ge m.

    Citation: The definition and problem are from Dehghan–Mollahajiaghaei, “On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs,” arXiv:1611.03181. The counterexample above is self-contained.

    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 construction is a valid counterexample. In the twice-subdivided K4K_4, χ(G)=3\chi(G)=3 since it has a proper 3-coloring and contains an odd 9-cycle. For each original edge ijij, the middle edge aijbija_{ij}b_{ij} has closed neighborhoods differing only by ii versus jj, so any closed distinguishing labeling forces f(i)≠f(j)f(i)\ne f(j). Hence the four original vertices need four distinct labels, so diss[G]≥4>χ(G)=3dis_s[G]\ge4>\chi(G)=3. This rigorously disproves the stated inequality. I found no evidence of an existing published resolution of this specific counterexample.

      Novelty assessment

      TYPE1

      Classification rationale: The counterexample is valid and gives an arbitrarily large gap by twice-subdividing KmK_m. However, the argument is a one-line observation from the definitions. Even though it answers a posed problem, the problem is quite specialized and the resolution is too short/routine to support a standalone journal paper. It would be suitable as an erratum, short note, or remark.

      Literature check: I found no source containing this counterexample or an equivalent unbounded-gap statement for diss(G)dis_s(G) versus χ(G)\chi(G). The original paper proves unboundedness for the sum-label parameter dis(G)dis(G) on bipartite graphs, but that is not the same as the strong color parameter diss(G)dis_s(G) in Problem 7. Searches of Semantic Scholar, DBLP, Crossref/OpenAlex/OpenCitations citation data, arXiv metadata, GitHub repositories/issues/discussions, and related “locally identifying coloring” literature found only the original paper and unrelated/adjacent coloring papers. Indexed citing papers concern weakly semiregular partitioning, dd-lucky numbers, and sum edge-coloring, not this problem.

      Citation: A. Dehghan and M. Mollahajiaghaei, “On the algorithmic complexity of adjacent vertex closed distinguishing colorings number of graphs,” Discrete Applied Mathematics 218 (2017), 82–97. DOI: 10.1016/j.dam.2016.10.028; arXiv:1611.03181.

      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.