Ban‐Linial's Conjecture and Halin Snarks
Xiaoyu Li, Rong‐Xia Hao, Yilun Luo, Siyan Liu · Journal of Graph Theory · 2026
ABSTRACT A 2‐bisection is a 2‐coloring of (not necessarily proper) such that each color class has the same cardinality, and each monochromatic component has at most 2 vertices. It was conjectured by Ban and Linial that every cubic graph admits a 2‐bisection, except for the Petersen graph. After discovering some examples, Esperet et al. [J. Graph Theory, 2017, 86(2), 149–158] further verified a conjecture for the family of bridgeless cubic graph that admits a 2‐bisection, except for the Petersen graph. Zerafa [J. Graph Theory, 2022, 101(3), 511–520] proved that each treelike snark admits a 2‐bisection. It is known that the family of Halin snarks is a superset of treelike snarks. In the same paper, Zerafa raised a problem that what assumption needed to be made with regard to the building block of a Halin snark for the verification of the 2‐bisection conjecture. This problem is solved in this paper and it is proved that each Halin snark admits a 2‐bisection if the multipole of the building blocks has an all‐2‐balanced and an ‐unbalanced 2‐coloring, where (see Section 2.2 for definitions). As corollaries, the 2‐bisection conjecture is further verified for several infinite families of Halin snarks including a superset of treelike snarks.