no. 16 · Tuesday 17 November 2026
An infinite family of minimally nonperfectly divisible graphs with a bisimplicial vertex
Abstract
We construct an explicit infinite family of minimally nonperfectly divisible graphs $G_t$, each with a bisimplicial vertex $v_t$ of degree four and a cutvertex. Thus the same family disproves Hoàng's conjectures excluding bisimplicial vertices and clique cutsets from such graphs. For every integer $t\geq1$, the graph $G_t$ has clique number three and satisfies \[ |V(G_t)|=93+30(t-1),\qquad |E(G_t)|=320+104(t-1). \] Deleting $v_t$ gives a perfectly divisible graph $H_t$ with an edge whose endpoints both lie outside the perfect part of every perfect division. This gives a negative answer to the prescribed-vertex question of Hu, Xu and Zhuang. The same graphs answer their second question affirmatively: each $H_t$ is perfectly divisible but not perfectly weight divisible. The cutvertex and weighted consequences were pointed out by Hu, Xu and Zhuang, who also observed that replacing one endpoint of the edge by two adjacent twins gives a minimally nonperfectly divisible graph with a homogeneous set.
- comments
- 11 pages, 1 figure. New proof of Lemma 2.2 using a recolouring argument and explicit partitions. Discussion revised in light of Hu--Xu--Zhuang (arXiv:2603.01967v3). Verification code and graph data: https://doi.org/10.5281/zenodo.24211586
- fields
- Combinatorics