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 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

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, 10.1080/00029890.1966.11970928.
    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 {I}sing 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