ProbXiv
sign in

The b-chromatic number of some tree-like graphs

Combinatorics · math.CO · posed by Ana Shirley Ferreira da Silva · open

1 attempt · 1 machine check

Statement

Let G be a tight graph such that:

  • For every edge (u,v)∈E(G)(u,v)\in E(G) , one of its endpoints is dense, and the other is non-dense, and

  • ∣N(u)∩N(v)∣≤1|N(u)\cap N(v)|\leq 1 , for all pair of vertices u,v∈D(G),u≠vu,v \in D(G),u≠v .Then, χb(G)=m(G)\chi_b(G) = m(G).

Context

Candidate 3 of the open problems stated in "The b-chromatic number of some tree-like 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 finite simple graphs, let m(G)m(G) be the largest kk such that at least kk vertices have degree at least k−1k-1; call vertices of degree at least m(G)−1m(G)-1 dense, and let D(G)D(G) be the set of dense vertices. Under the standard definition, a tight graph has exactly m(G)m(G) dense vertices, each of degree m(G)−1m(G)-1. The conjecture claims that if a tight graph GG satisfies

    every edge has one dense and one non-dense endpoint\text{every edge has one dense and one non-dense endpoint}

    and

    ∣N(u)∩N(v)∣≤1for all distinct u,v∈D(G),|N(u)\cap N(v)|\le 1\quad\text{for all distinct }u,v\in D(G),

    then

    χb(G)=m(G).\chi_b(G)=m(G).

    Result: The conjecture is false.

    Let GG be the subdivision graph of K4K_4. More explicitly, let

    D={1,2,3,4},U={uij:1≤i<j≤4},D=\{1,2,3,4\},\qquad U=\{u_{ij}:1\le i<j\le 4\},

    and join uiju_{ij} exactly to ii and jj.

    Then every vertex in DD has degree 33, every vertex in UU has degree 22, so

    m(G)=4,m(G)=4,

    and D(G)=DD(G)=D. Thus GG is tight. Every edge joins DD to UU, and for distinct i,j∈Di,j\in D,

    N(i)∩N(j)={uij},N(i)\cap N(j)=\{u_{ij}\},

    so the common-neighborhood condition holds.

    Suppose GG had a 44-b-coloring. A 44-b-vertex must have degree at least 33, so all four b-vertices must be the four vertices of DD. Hence the vertices of DD receive four distinct colors and each is a b-vertex.

    Fix a color cc. Let dc∈Dd_c\in D be the dense vertex colored cc. Each of the other three dense vertices must see color cc exactly once among its three neighbors, while dcd_c sees color cc zero times. Thus there are exactly 33 incidences between dense vertices and non-dense vertices colored cc. But every non-dense vertex has degree 22, so the number of such incidences contributed by vertices colored cc is even. Contradiction.

    Therefore χb(G)≠4=m(G)\chi_b(G)\ne 4=m(G). In fact χb(G)=3\chi_b(G)=3, so the asserted equality fails.

    Citation: No external citation is needed; the counterexample 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 KNOWN

      PASS

      The counterexample is valid. The subdivision graph of K4K_4 has m(G)=4m(G)=4, exactly four dense vertices of degree 33, is tight, has every edge between a dense and a non-dense vertex, and any two dense vertices share exactly one neighbor.

      The no-44-b-coloring argument is rigorous: in any 44-b-coloring, all four b-vertices must be the four dense vertices, with distinct colors. For any color cc, the other three dense vertices must each see color cc once, giving exactly 33 incidences from dense vertices to non-dense vertices of color cc. But each non-dense vertex has degree 22, so such incidences must be even, a contradiction. Thus χb(G)≠m(G)\chi_b(G)\ne m(G), disproving the conjecture.

      Novelty assessment

      KNOWN

      Classification rationale: The accepted counterexample is already covered in the literature: the subdivision graph of K4K_4 is the case n=4n=4 of the subdivision graph Sn1S^1_n of KnK_n, whose b-chromatic number was explicitly stated as n−1n-1. Thus χb(S(K4))=3\chi_b(S(K_4))=3, exactly the accepted solution’s conclusion.

      Literature check: I found no exact hit for “Conjecture 2.13” plus “b-chromatic”, but searching for the specific graph led to an existing paper on subdivision graphs of complete graphs. Jeeva and Selvakumar define Sn1S^1_n as the graph obtained from KnK_n by inserting one new vertex in every edge, and Observation 3.3 states b(Sn1)=n−1b(S^1_n)=n-1 for n≥4n\ge4. The case n=4n=4 is precisely the subdivision graph of K4K_4.

      Citation: A. Jeeva and R. Selvakumar, “The b-chromatic number of subdivision graph of complete graph,” International Journal of Pure and Applied Mathematics 113(9) (2017), 185–191, Observation 3.3. Available at: https://acadpubl.eu/jsi/2017-113-pp/articles/9/21.pdf.

      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.