×

A differential equation arising in chromatic sum theory. (English) Zbl 0535.05035

Combinatorics, graph theory and computing, Proc. 14th Southeast. Conf., Boca Raton/Flo. 1983, Congr. Numerantium 40, 263-275 (1983).
[For the entire collection see Zbl 0523.00001.]
Let T denote a rooted triangulation of the sphere, multiple edges allowed but not loops, with 2n faces. A triangulation is rooted when an edge is chosen, a direction is assigned to the edge and a left right orientation is chosen with respect to the directed edge. Let P(T,\(\lambda)\) denote the chromatic polynomial of the graph of T and let \(h_ n\) denote the sum of P(T,\(\lambda)\) over all rooted triangulations of the sphere with 2n faces. Starting from W. T. Tutte’s nonlinear differential that the generating function, h(t), of the \(h_ n\) satisfies we show that for \(\lambda\geq 5\) or \(3(5/11)<\lambda<4\) the estimate \(h_ n\sim CR^{- n}/n^{5/2}\), \(n\to \infty\), \(\lambda\) fixed, is valid where \(R<1\) is the radius of convergence of h(t) and C is a positive constant defined explicitly in terms of R, \(\lambda\), and h’(R).

MSC:

05C30 Enumeration in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory

Citations:

Zbl 0523.00001