Geodesic
Beta invariant and chromatic uniqueness of wheels
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 269-280 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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].
Keywords: chromatic uniqueness of graphs, beta invariant, characteristic polynomial, 2-sum, 3-sum, matroids 
@article{DMGT_2024_44_1_a12,
     author = {Lee, Sooyeon and Wu, Haidong},
     title = {Beta invariant and chromatic uniqueness of wheels},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {269--280},
     year = {2024},
     volume = {44},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a12/}
}
TY  - JOUR
AU  - Lee, Sooyeon
AU  - Wu, Haidong
TI  - Beta invariant and chromatic uniqueness of wheels
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 269
EP  - 280
VL  - 44
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a12/
LA  - en
ID  - DMGT_2024_44_1_a12
ER  - 
%0 Journal Article
%A Lee, Sooyeon
%A Wu, Haidong
%T Beta invariant and chromatic uniqueness of wheels
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 269-280
%V 44
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a12/
%G en
%F DMGT_2024_44_1_a12
Lee, Sooyeon; Wu, Haidong. Beta invariant and chromatic uniqueness of wheels. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 269-280. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a12/

[1] S. Akbari, S. Alikhani and Y.-h. Peng, Characterization of graphs using domination polynomials, European J. Combin. 31 (2010) 1714–1724. https://doi.org/10.1016/j.ejc.2010.03.007

[2] S. Akbari and M.R. Oboudi, Cycles are determined by their domination polynomials, Ars Combin. 116 (2014) 353–358.

[3] Z.Y. Al-Rekaby and A.J.M. Khalaf, On chromaticity of wheels, Int. J. Math. Comput. Sci. 8 (2014) 1149–1152.

[4] J. Azarija, Some Results from Algebraic Graph Theory, PhD. Thesis (University of Ljubljana, 2016).

[5] I. Beaton, J.I. Brown and B. Cameron, Independence equivalence classes of paths and cycles, Australas. J. Combin. 75 (2019) 127–145.

[6] J.K. Benashski, R.R. Martin, J.T. Moore and L. Traldi, On the {\beta}-invariant for graphs, Congr. Numer. 109 (1995) 211–221.

[7] K. Boyer, B. Brimkov, S. English, D. Ferrero, A. Keller, R. Kirsch, M. Phillips and C. Reinhart, The zero forcing polynomial of a graph, Discrete Appl. Math. 258 (2019) 35–48. https://doi.org/10.1016/j.dam.2018.11.033

[8] B. Bollobás, Modern Graph Theory (Springer-Verlag, New York, 1998).

[9] T.H. Brylawski, A combinatorial model for series-parallel networks, Trans. Amer. Math. Soc. 154 (1971) 1–22. https://doi.org/10.1090/S0002-9947-1971-0288039-7

[10] C.-Y. Chao and E.G. Whitehead Jr., On chromatic equivalence of graphs, in: Theory and Applications of Graphs, Lecture Notes in Math., 642, Y. Alavi and D.R. Lick (Ed(s)), (Springer Berlin Heidelberg 1978) 121–131. https://doi.org/10.1007/BFb0070369

[11] C.-Y. Chao and G.E. Whitehead Jr., Chromatically unique graphs, Discrete Math. 27 (1979) 171–177. https://doi.org/10.1016/0012-365X(79)90107-9

[12] H.H. Crapo, A higher invariant for matroids, J. Combin. Theory 2 (1967) 406–417. https://doi.org/10.1016/S0021-9800(67)80051-6

[13] F.M. Dong, K.M. Koh and K.L. Teo, Chromatic Polynomials and Chromaticity of Graphs (World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2005).

[14] A. de Mier and M. Noy, On graphs determined by their Tutte polynomials, Graphs Combin. 20 (2004) 105–119. https://doi.org/10.1007/s00373-003-0534-z

[15] Y. Duan, H. Wu and Q. Yu, On chromatic and flow polynomial unique graphs, Discrete Appl. Math. 156 (2008) 2300–2309. https://doi.org/10.1016/j.dam.2007.10.010

[16] S. Lee and H. Wu, Bounding the beta invariant of 3-connected matroids, Discrete Math. 345 (2022) 112638. https://doi.org/10.1016/j.disc.2021.112638

[17] N.-Z. Li and G.E. Whitehead Jr., The chromatic uniqueness of {W10}, Discrete Math. 104 (1992) 197–199. https://doi.org/10.1016/0012-365X(92)90334-C

[18] J.A. Makowsky and V. Rakita, On weakly distinguishing graph polynomials, Discrete Math. Theor. Comput. Sci. 21 (2019) 4–10. https://doi.org/10.23638/DMTCS-21-1-4

[19] J.G. Oxley, On Crapo's beta invariant for matroids, Stud. Appl. Math. 66 (1982) 267–277. https://doi.org/10.1002/sapm1982663267

[20] J. Oxley, Matroid Theory (Oxford University Press, Oxford, 2011). https://doi.org/10.1093/acprof:oso/9780198566946.001.0001

[21] R.C. Read, A note on the chromatic uniqueness of {W10}, Discrete Math. 69 (1988) 317. https://doi.org/10.1016/0012-365X(88)90061-1

[22] S.-J. Xu and N.-Z. Li, The chromaticity of wheels, Discrete Math. 51 (1984) 207–212. https://doi.org/10.1016/0012-365X(84)90072-4

[23] W.T. Tutte, Connectivity in matroids, Canad. J. Math. 18 (1966) 1301–1324. https://doi.org/10.4153/CJM-1966-129-2

[24] H. Whitney, 2-isomorphic graphs, Amer. J. Math. 55 (1933) 1–4.