ProbXiv
sign in

Some families of chromatically unique bipartite graphs

Combinatorics · math.CO · posed by Xiebin Chen · open

1 attempt · 1 machine check

Statement

For every r ≥0 and every h≥h0(r), where h0(r) depends on r, there is an integer p1(h,r) depending on h and r, such that for every p≥p1(h,r), each member of K^{-r}(p,p+h) is χ-unique.

Context

Candidate 1 of the open problems stated in "Some families of chromatically unique bipartite 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: in finite simple graphs, K−r(p,q)K^{-r}(p,q) denotes the family of graphs obtained from Kp,qK_{p,q} by deleting exactly rr edges. A graph is χ\chi-unique if every graph with the same chromatic polynomial is isomorphic to it. The conjecture asserts

    ∀r≥0 ∃h0(r) ∀h≥h0(r) ∃p1(h,r) ∀p≥p1(h,r),\forall r\ge 0\ \exists h_0(r)\ \forall h\ge h_0(r)\ \exists p_1(h,r)\ \forall p\ge p_1(h,r),

    every member of K−r(p,p+h)K^{-r}(p,p+h) is χ\chi-unique. This is the standard meaning of the notation in this bipartite chromatic-uniqueness context.

    Result: The conjecture is false. A counterexample exists already for r=8r=8, for every h≥1h\ge1 and all sufficiently large pp.

    Let q=p+hq=p+h. In Kp,qK_{p,q}, delete edges according to the following 4×44\times4 00-11 matrix, with rows in the pp-part and columns in the qq-part:

    D=(1010101101011000).D= \begin{pmatrix} 1&0&1&0\\ 1&0&1&1\\ 0&1&0&1\\ 1&0&0&0 \end{pmatrix}.

    Let D⊤D^\top be its transpose. Embed both in the first four vertices of each part, and define

    G=Kp,q−D,G′=Kp,q−D⊤.G=K_{p,q}-D,\qquad G'=K_{p,q}-D^\top .

    Both lie in K−8(p,q)K^{-8}(p,q).

    For any deleted-edge graph D⊆Kp,qD\subseteq K_{p,q}, repeated deletion-contraction gives

    P(Kp,q−D,t)=∑S⊆E(D)P(Kp,q/S,t).P(K_{p,q}-D,t)=\sum_{S\subseteq E(D)} P(K_{p,q}/S,t).

    A subset SS contributes nonzero precisely when each nontrivial component of SS is a complete bipartite graph. If such an SS covers aa left vertices and bb right vertices and has cc nontrivial components, then

    P(Kp,q/S,t)=(t)c P(Kp−a,q−b,t−c).P(K_{p,q}/S,t)=(t)_c\,P(K_{p-a,q-b},t-c).

    Thus the chromatic polynomial depends only on the counts ND(a,b,c)N_D(a,b,c) of such admissible subsets.

    For the above DD, the nonzero counts are:

    (a,b,c)ND(a,b,c)(0,0,0)1(1,1,1)8(1,2,1),(2,1,1)5(1,3,1),(3,1,1)1(2,2,1)1(2,2,2)18(2,3,2),(3,2,2)15(2,4,2),(4,2,2)3(3,3,2)8(3,3,3)12(3,4,2),(4,3,2)1(3,4,3),(4,3,3)8(4,4,3)4(4,4,4)1.\begin{array}{c|c} (a,b,c)&N_D(a,b,c)\\ \hline (0,0,0)&1\\ (1,1,1)&8\\ (1,2,1),(2,1,1)&5\\ (1,3,1),(3,1,1)&1\\ (2,2,1)&1\\ (2,2,2)&18\\ (2,3,2),(3,2,2)&15\\ (2,4,2),(4,2,2)&3\\ (3,3,2)&8\\ (3,3,3)&12\\ (3,4,2),(4,3,2)&1\\ (3,4,3),(4,3,3)&8\\ (4,4,3)&4\\ (4,4,4)&1 . \end{array}

    The table is symmetric in a,ba,b. Since transposition sends ND(a,b,c)N_D(a,b,c) to ND⊤(b,a,c)N_{D^\top}(b,a,c), we get

    ND(a,b,c)=ND⊤(a,b,c)N_D(a,b,c)=N_{D^\top}(a,b,c)

    for all triples. Hence

    P(G,t)=P(G′,t).P(G,t)=P(G',t).

    But G≇G′G\not\cong G' when p≥7p\ge7 and q>pq>p. Indeed both graphs are connected bipartite, so an isomorphism must preserve the two part sizes. It would therefore induce a side-preserving isomorphism between DD and D⊤D^\top. No such isomorphism exists: in DD, the unique left vertex of deletion-degree 11 is adjacent to the unique right vertex of deletion-degree 33; in D⊤D^\top, the unique left vertex of deletion-degree 11 is adjacent to a right vertex of deletion-degree 22.

    Thus for every h≥1h\ge1 and every p≥7p\ge7, K−8(p,p+h)K^{-8}(p,p+h) contains a graph that is not χ\chi-unique. Therefore no h0(8)h_0(8) can satisfy the conjecture.

    Citation: No external resolution is used; the counterexample above is explicit.

    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 TYPE2

      PASS

      The disproof is mathematically sound. The deletion–contraction expansion is correctly specialized: only subsets whose components are complete bipartite contribute, and their contribution depends only on (a,b,c)(a,b,c). The stated finite count table for the chosen 8-edge deletion pattern is symmetric, so Kp,q−DK_{p,q}-D and Kp,q−D⊤K_{p,q}-D^\top have the same chromatic polynomial. For q>pq>p, connectedness forces any isomorphism to preserve bipartition sizes, and the deletion patterns are not side-preservingly isomorphic, so the graphs are nonisomorphic. Thus the conjecture is false for r=8r=8.

      A literature search found related small-rr uniqueness papers but no prior similar counterexample or stronger disproof.

      Novelty assessment

      TYPE2

      Classification rationale: The result appears genuinely new and gives an explicit counterexample to a published conjecture, already with r=8r=8. Although the proof is short and computational/finite in flavor, it resolves the conjecture negatively and would plausibly support a short standalone note in a standard graph theory/combinatorics journal. It is not TYPE3: the conjecture is fairly specialized and the method is not a broad major advance.

      Literature check: I found no prior occurrence of this counterexample or any stronger disproof. Searches of scholarly indexes and web results for Chen’s conjecture, K−r(p,q)K^{-r}(p,q), K−8K^{-8}, h0(r)h_0(r), p1(h,r)p_1(h,r), and “chromatically unique complete bipartite graphs with edges deleted” led only to positive/partial uniqueness papers. In particular, Dong–Koh–Teo–Little–Hendy and Roslan/Hasni–Peng prove uniqueness for various structured deletion graphs or large maximum-degree cases, but they do not cover this 88-edge, maximum deletion-degree 33 nonunique construction.

      Citation: No prior citation found for the counterexample. Relevant literature includes X. Chen, “Some families of chromatically unique bipartite graphs,” Discrete Math. 184 (1998), 245–252, doi:10.1016/S0012-365X(97)00203-3; F.M. Dong et al., “Sharp bounds for the number of 3-independent partitions and the chromaticity of bipartite graphs,” J. Graph Theory 37 (2001), 48–77; and R. Hasni/Y.H. Peng, “Chromatic Uniqueness of Complete Bipartite Graphs with Certain Edges Deleted II,” Punjab Univ. J. Math. 43 (2011), 1–8.

      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.