Beta invariant and chromatic uniqueness of wheels

Lee, Sooyeon ; Wu, Haidong 

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 269-280

Résumé

A graph G is chromatically unique if its chromatic polynomial completely determines the graph. An n-spoked wheel, W_n, is shown to be chromatically unique when n≥ 4 is even [S.-J. Xu and N.-Z. Li, The chromaticity of wheels, Discrete Math. 51 (1984) 207–212]. When n is odd, this problem is still open for n≥ 15 since 1984, although it was shown by different researchers that the answer is no for n=5, 7, yes for n=3, 9, 11, 13, and unknown for other odd n. We use the beta invariant of matroids to prove that if M is a 3-connected matroid such that |E(M)| = |E(W_n)| and β(M) = β(M(W_n)), where β(M) is the beta invariant of M, then M ≅ M(W_n). As a consequence, if G is a 3-connected graph such that the chromatic (or flow) polynomial of G equals to the chromatic (or flow) polynomial of a wheel, then G is isomorphic to the wheel. The examples for n=3, 5 show that the 3-connectedness condition may not be dropped. We also give a splitting formula for computing the beta invariants of general parallel connection of two matroids as well as the 3-sum of two binary matroids. This generalizes the corresponding result of Brylawski [A combinatorial model for series-parallel networks, Trans. Amer. Math. Soc. 154 (1971) 1–22].

Détail

Keywords: chromatic uniqueness of graphs, beta invariant, characteristic polynomial, 2-sum, 3-sum, matroids