Sivaraman's Perfect-Divisibility Characterization Question
Sivaraman asked whether perfect divisibility is characterized by its chromatic consequence: is a graph perfectly divisible if and only if for every induced subgraph of ? False: the Paley graph satisfies the chromatic bound hereditarily but is not perfectly divisible.
- Result
- Disproved
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Construction
- Field
- Graph theory - chi-boundedness
- Posed by
- Vaidy Sivaraman
- Year posed
- 2026
- Years open
- 0y
- Solved
- 2026-08-14
- Model
- ChatGPT
- Vendor
- OpenAI
- Collaborators
- Zhiyu Wang, Weihao Xia
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 4 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The acknowledgement states that the Paley graph P(17) - the counterexample witness - was identified during exploratory use of ChatGPT and subsequently verified by the authors, with ChatGPT also used for language polishing and generating the verification code. All arguments and computations were checked by the authors.
Verification
Checked by this site on 17 August 2026 against the paper's LaTeX (arXiv:2608.14519, Wang-Xia): the question is stated as Question 1 with attribution to Sivaraman by personal communication, the negative answer via P(17) is Theorem-level, and the acknowledgement is verbatim as quoted. The P(17) computation was not re-run here. The paper's larger content - perfect and linear divisibility of chair-free graphs - is human work outside this entry's claim. Days old, no independent review.