Geodesic
Explicit formulas for chromatic polynomials of some series-parallel graphs
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 160 (2018) no. 2, pp. 339-349 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The main goal of our paper is to present explicit formulas for chromatic polynomials of some planar series-parallel graphs (sp-graphs). The necklace-graph considered in this paper is the simplest non-trivial sp-graph. We have provided the explicit formula for calculating the chromatic polynomial of common sp-graphs. In addition, we have presented the explicit formulas for calculating chromatic polynomials of the ring of the necklace graph and the necklace of the necklace graph. Chromatic polynomials of the necklace graph and the ring of the necklace graph have been initially obtained by transition to the dual graph and the subsequent using of the flow polynomial. We have also used the technique of finite Fourier transformations. The use of the partition function of the Potts model is a more general way to evaluate chromatic polynomials. In this method, we have used the parallel- and series-reduction identities that were introduced by A. Sokal. We have developed this idea and introduced the transformation of the necklace-graph reduction. Using this transformation makes it easier to calculate chromatic polynomials for the necklace-graph, the ring of the necklace graph, as well as allows to calculate the chromatic polynomial of the necklace of the necklace graph.
Keywords: chromatical polynomial, partition function of Potts model, series-parallel graph, necklace graph.
Mots-clés : Tutte polynomial, Fourier transform 
@article{UZKU_2018_160_2_a14,
     author = {E. Yu. Lerner and S. A. Mukhamedjanova},
     title = {Explicit formulas for chromatic polynomials of some series-parallel graphs},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {339--349},
     year = {2018},
     volume = {160},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2018_160_2_a14/}
}
TY  - JOUR
AU  - E. Yu. Lerner
AU  - S. A. Mukhamedjanova
TI  - Explicit formulas for chromatic polynomials of some series-parallel graphs
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2018
SP  - 339
EP  - 349
VL  - 160
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UZKU_2018_160_2_a14/
LA  - en
ID  - UZKU_2018_160_2_a14
ER  - 
%0 Journal Article
%A E. Yu. Lerner
%A S. A. Mukhamedjanova
%T Explicit formulas for chromatic polynomials of some series-parallel graphs
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2018
%P 339-349
%V 160
%N 2
%U http://geodesic.mathdoc.fr/item/UZKU_2018_160_2_a14/
%G en
%F UZKU_2018_160_2_a14
E. Yu. Lerner; S. A. Mukhamedjanova. Explicit formulas for chromatic polynomials of some series-parallel graphs. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 160 (2018) no. 2, pp. 339-349. http://geodesic.mathdoc.fr/item/UZKU_2018_160_2_a14/

[1] Biggs N., Algebraic Graph Theory, Cambridge Univ. Press, 1993, 205 pp. | MR

[2] Distel R., Graph Theory, Springer, 2005, 431 pp. | MR

[3] Dong F. M., Koh K. M., Teo K. L., Chromatic Polynomials and Chromaticity of Graphs, World Sci. Publ., 2005, 384 pp. | DOI | MR | Zbl

[4] Tutte W. T., Graph Theory, Adv. Book Program, Addison-Wesley Pub. Co., 1984, 333 pp. | MR | Zbl

[5] Kuptsov A. P., Lerner E. Y., Mukhamedjanova S. A., “Flow polynomials as Feynman amplitudes and their $\alpha$-representation”, Electron. J. Comb., 24:1 (2017), P1.11, 19 pp. | MR | Zbl

[6] Sokal A. D., “The multivariate Tutte polynomial (alias Potts model) for graphs and matroids”, Surv. Comb., 327 (2005), 173–226 | DOI | MR | Zbl

[7] Goodall A. D., “Some new evaluations of the Tutte polynomial”, J. Comb. Theory, Ser. B, 96:2 (2006), 207–224 | DOI | MR | Zbl

[8] Royle G. F., Sokal A. D., “Linear bound in terms of maxmaxflowfor the chromatic roots of series-parallel graphs”, SIAM J. Discrete Math., 29:4 (2015), 2117–2159 | DOI | MR | Zbl