ProbXiv
sign in
machine only

Chromatic spectrum of some classes of2-regular bipartite colored graphs

Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.

chromatic-spectrum-of-some-classes-of2-regular-bipartite-colored-graphsRepresentation Theorymath.RTmath.SPposed by Muhammad Imran, Yasir Ali, Mehar Ali Malik, Kiran Hasnatrecorded: open · 1 machine check, unexamined

1 attempt · 1 machine check · no person has looked

Statement

Determination of ξ_G(λ_χ) for general chromatic characteristic polynomials of all 2-regular bipartite graphs is still in progress.

Context

Candidate 1 of the open problems stated in "Chromatic spectrum of some classes of2-regular bipartite colored graphs", extracted for the Scalable Mathematical Discovery run.

People

no project yet · nobody looking

Projects

none yet

Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.

begin a project on this problem →

Interest

nobody looking

Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.

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 finite simple 22-regular bipartite graph GG, determine the chromatic characteristic polynomial

    ξG(λχ)=det⁡(λχI−Aχ(G)),\xi_G(\lambda_\chi)=\det(\lambda_\chi I-A_\chi(G)),

    where, for a proper 22-coloring with colors c1,c2c_1,c_2,

    (Aχ)uv={1,u≠v, uv∈E(G),0,u≠v, uv∉E(G),1,u=v, φ(u)=c1,2,u=v, φ(u)=c2.(A_\chi)_{uv}= \begin{cases} 1,&u\neq v,\ uv\in E(G),\\ 0,&u\neq v,\ uv\notin E(G),\\ 1,&u=v,\ \varphi(u)=c_1,\\ 2,&u=v,\ \varphi(u)=c_2. \end{cases}

    This is the standard chromatic adjacency matrix convention in this literature. If the paper uses det⁡(Aχ−λχI)\det(A_\chi-\lambda_\chi I), the answer is unchanged because every such graph has even order.

    Result: Every finite simple 22-regular bipartite graph is a disjoint union

    G=⨆i=1rC2mi,mi≥2.G=\bigsqcup_{i=1}^r C_{2m_i},\qquad m_i\ge 2.

    Then

    ξG(λχ)=∏i=1r∏k=0mi−1(λχ2−3λχ−2cos⁡2πkmi).\boxed{ \xi_G(\lambda_\chi) = \prod_{i=1}^r\prod_{k=0}^{m_i-1} \left(\lambda_\chi^2-3\lambda_\chi -2\cos\frac{2\pi k}{m_i}\right). }

    Equivalently,

    ξG(λχ)=∏i=1r2[Tmi ⁣(λχ2−3λχ2)−1],\xi_G(\lambda_\chi) = \prod_{i=1}^r 2\left[ T_{m_i}\!\left(\frac{\lambda_\chi^2-3\lambda_\chi}{2}\right)-1 \right],

    where TmT_m is the Chebyshev polynomial of the first kind.

    Hence the chromatic eigenvalues are

    λχ,i,k±=3±9+8cos⁡(2πk/mi)2,k=0,…,mi−1.\lambda_{\chi,i,k}^{\pm} = \frac{3\pm\sqrt{9+8\cos(2\pi k/m_i)}}{2}, \qquad k=0,\dots,m_i-1.

    Proof. For a component C2mC_{2m}, label vertices alternately

    x0,y0,x1,y1,…,xm−1,ym−1,x_0,y_0,x_1,y_1,\dots,x_{m-1},y_{m-1},

    with xjx_j color c1c_1, yjy_j color c2c_2. Ordering all xx’s first and yy’s second gives

    Aχ(C2m)=(ImBBT2Im),B=Im+Pm,A_\chi(C_{2m})= \begin{pmatrix} I_m&B\\ B^T&2I_m \end{pmatrix}, \qquad B=I_m+P_m,

    where PmP_m is the cyclic permutation matrix. Thus

    λχI−Aχ=((λχ−1)Im−B−BT(λχ−2)Im).\lambda_\chi I-A_\chi= \begin{pmatrix} (\lambda_\chi-1)I_m&-B\\ -B^T&(\lambda_\chi-2)I_m \end{pmatrix}.

    By the Schur complement, as a polynomial identity,

    ξC2m(λχ)=det⁡ ⁣((λχ−1)(λχ−2)Im−BTB).\xi_{C_{2m}}(\lambda_\chi) = \det\!\left((\lambda_\chi-1)(\lambda_\chi-2)I_m-B^TB\right).

    Now

    BTB=(I+PmT)(I+Pm)=2Im+Pm+PmT.B^TB=(I+P_m^T)(I+P_m)=2I_m+P_m+P_m^T.

    The eigenvalues of PmP_m are e2πik/me^{2\pi i k/m}, so the eigenvalues of BTBB^TB are

    2+2cos⁡2πkm.2+2\cos\frac{2\pi k}{m}.

    Therefore

    ξC2m(λχ)=∏k=0m−1(λχ2−3λχ−2cos⁡2πkm).\xi_{C_{2m}}(\lambda_\chi) = \prod_{k=0}^{m-1} \left(\lambda_\chi^2-3\lambda_\chi -2\cos\frac{2\pi k}{m}\right).

    For disconnected GG, Aχ(G)A_\chi(G) is block diagonal over components, so the characteristic polynomials multiply. Swapping the two colors on any component merely interchanges the diagonal blocks ImI_m and 2Im2I_m, leaving the same determinant.

    Citation: No prior general formula is used here. Problem source: Imran, Ali, Malik, and Hasnat, “Chromatic spectrum of some classes of 2-regular bipartite colored graphs,” Journal of Intelligent & Fuzzy Systems, DOI: 10.3233/JIFS-210066.

    Reviews

    0 human 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 proof correctly addresses the finite simple case of the stated problem under the standard chromatic adjacency-matrix convention. A finite 2-regular bipartite graph is a disjoint union of even cycles, and the block/Fourier computation for each C2mC_{2m} is valid; characteristic polynomials then multiply over components. Color swaps do not affect the determinant. I see no fatal gap or mismatch, and no prior general formula was evident from the available literature metadata.

      Novelty assessment

      TYPE1

      Classification rationale: The formula appears genuinely new in this niche “chromatic spectrum” terminology, but it is very minor. The proof is a routine reduction: every finite simple 2-regular bipartite graph is a disjoint union of even cycles, and each cycle is handled by a standard block-circulant/Fourier diagonalization; disconnected components multiply. This would at most support a short note or addendum, not a standalone standard combinatorics paper.

      Literature check: I found no prior publication giving the general formula. The original 2021 paper treats only three classes and states extension to general 2-regular bipartite colored graphs as future work. OpenAlex and Scopus list zero citations to the paper. Searches for the exact title, “chromatic spectrum” + “2-regular bipartite,” “chromatic spectrum” + “colored graph,” “chromatic adjacency matrix,” “chromatic characteristic polynomial,” and formula fragments such as “lambda^2-3lambda-2cos” did not reveal any later note, preprint, forum post, or stronger published result; results led essentially only to the original article metadata pages.

      Citation: Muhammad Imran, Yasir Ali, Mehar Ali Malik, Kiran Hasnat, “Chromatic spectrum of some classes of 2-regular bipartite colored graphs,” Journal of Intelligent & Fuzzy Systems 41(1), 1125–1133, 2021. DOI: 10.3233/JIFS-210066.

      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.

    Endorsements

    0 endorsements

    No one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.

    Discussion of this attempt

    no comments

Discussion

no comments

Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.

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