[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

B. Durhuus

Bergfinnur Durhuus

Department of Mathematical Sciences, University of Copenhagen

email: durhuus@math.ku.dk

0000-0002-0450-6792

A. Lucia

Angelo Lucia

Walter Burke Institute for Theoretical Physics and Institute for Quantum Information & Matter, California Institute of Technology

email: alucia@caltech.edu

0000-0003-1709-1220

Title:

Recursion relations for chromatic coefficients for graphs and hypergraphs

PDF

Source:

Discussiones Mathematicae Graph Theory 42(1) (2022) 101-121

Received: 2019-03-25 , Revised: 2019-07-06 , Accepted: 2019-07-31 , Available online: 2019-11-18 , https://doi.org/10.7151/dmgt.2248

Abstract:

We establish a set of recursion relations for the coefficients in the chromatic polynomial of a graph or a hypergraph. As an application we provide a generalization of Whitney's broken cycle theorem for hypergraphs, as well as deriving an explicit formula for the linear coefficient of the chromatic polynomial of the $r$-complete hypergraph in terms of roots of the Taylor polynomials for the exponential function.

Keywords:

chromatic polynomials, hypergraphs, broken cycles

References:

  1. C. Berge, Hypergraphs (North Holland, Amsterdam, 1989).
  2. G.D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. of Math. (2) 14 (1912–1913) 42–46.
    https://doi.org/10.2307/1967597
  3. A. Blass and B.E. Sagan, Bijective proofs of two broken circuit theorems, J. Graph Theory 10 (1986) 15–21.
    https://doi.org/10.1002/jgt.3190100104
  4. J.D. Buckholtz, A characterization of the exponential series, Amer. Math. Monthly 73 (1966) 121–123.
    https://doi.org/10.2307/2313761
  5. Cs. Bujtás, Zs. Tuza and V.I. Voloshin, Hypergraph colouring, in: Topics in Chromatic Graph Theory, L.W. Beineke and R.J. Wilson (Ed(s)), (Cambridge University Press, Cambridge 2015) 230–254.
    https://doi.org/10.1017/CBO9781139519793.014
  6. B. Conrey and A. Ghosh, On the zeros of the Taylor polynomials associated with the exponential function, Amer. Math. Monthly 95 (1988) 528–533.
    https://doi.org/10.2307/2322757
  7. J. Dieudonné, Sur les zéros des polynomes-sections de $e^x$, Bull. Sci. Math. 70 (1935) 333–351.
  8. K. Dohmen, A Broken-Circuits-Theorem for hypergraphs, Arch. Math. (Basel) 64 (1995) 159–162.
    https://doi.org/10.1007/BF01196637
  9. K. Dohmen, An improvement of the inclusion-exclusion principle, Arch. Math. (Basel) 72 (1999) 298–303.
    https://doi.org/10.1007/s000130050336
  10. K. Dohmen, An inductive proof of Whitney's broken circuit theorem, Discuss. Math. Graph Theory 31 (2011) 577–586.
    https://doi.org/10.7151/dmgt.1561
  11. K. Dohmen and M. Trinks, An abstraction of Whitney's Broken Circuit Theorem, Electron. J. Combin. 21(4) (2014) #P4.32.
    https://doi.org/10.37236/4356
  12. F.M. Dong, K.M. Koh and K.L. Teo, Chromatic Polynomials and Chromaticity of Graphs (World Scientific, 2005).
    https://doi.org/10.1142/5814
  13. S. Friedli and Y. Velenik, Statistical Mechanics of Lattice Systems: A Concrete Mathematical Introduction (Cambridge University Press, Cambridge, 2017).
    https://doi.org/10.1017/9781316882603
  14. J. Huh, Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, J. Amer. Math. Soc. 25 (2012) 907–927.
    https://doi.org/10.1090/S0894-0347-2012-00731-0
  15. D.J. Newman and T.J. Rivlin, The zeros of the partial sums of the exponential function, J. Approx. Theory 5 (1972) 405–412.
    https://doi.org/10.1016/0021-9045(72)90007-X
  16. D.J. Newman and T.J. Rivlin, Correction: The zeros of the partial sums of the exponential function, J. Approx. Theory 16 (1976) 299–300.
    https://doi.org/10.1016/0021-9045(76)90061-7
  17. C.E. Pfister, Large deviations and phase separation in the two-dimensional Ising model, Helv. Phys. Acta 64 (1991) 953–1054.
  18. I.E. Pritsker and R.S. Varga, The Szegö curve, zero distribution, and weighted approximation, Trans. Amer. Math. Soc. 349 (1997) 4085–4105.
    https://doi.org/10.1090/S0002-9947-97-01889-8
  19. R.C. Read, An introduction to chromatic polynomials, J. Combin. Theory 4 (1968) 52–71.
    https://doi.org/10.1016/S0021-9800(68)80087-0
  20. A.D. Scott and A.D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lovász Local Lemma, J. Stat. Phys. 118 (2005) 1151–1261.
    https://doi.org/10.1007/s10955-004-2055-4
  21. G. Szegö, Über eine Eigenschaft der Exponentialreihe, Sitzungsber. Berl. Math. Ges. 23 (1924) 50–64.
  22. M. Trinks, A note on a broken-cycle theorem for hypergraphs, Discuss. Math. Graph Theory 34 (2014) 641–646.
    https://doi.org/10.7151/dmgt.1734
  23. D. Ueltschi, Cluster expansions and correlation functions, Mosc. Math. J. 4 (2004) 511–522.
    https://doi.org/10.17323/1609-4514-2004-4-2-511-522
  24. R.S. Varga, A.J. Carpenter and B.W. Lewis, The dynamical motion of the zeros of the partial sums of $e^z$, and its relationship to discrepancy theory, Electron. Trans. Numer. Anal. 30 (2008) 128–143.
  25. V.I. Voloshin, The mixed hypergraphs, Comput. Sci. J. Moldova 1 (1993) 45–52.
  26. P. Walker, The zeros of the partial sums of the exponential series, Amer. Math. Monthly 110 (2003) 337–339.
    https://doi.org/10.1080/00029890.2003.11919971
  27. H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. (N.S.) 38 (1932) 572–579.
    https://doi.org/10.1090/S0002-9904-1932-05460-X
  28. S.M. Zemyan, On the zeroes of the nth partial sum of the exponential series, Amer. Math. Monthly 112 (2005) 891–909.
    https://doi.org/10.2307/30037629
  29. A.A. Zykov, Hypergraphs, Russian Math. Surveys 29 (1974) 89–156.
    https://doi.org/10.1070/RM1974v029n06ABEH001303

Close