×

Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph. (English) Zbl 0861.05027

Summary: An upper bound is given on the number of acyclic orientations of a graph, in terms of the spectrum of its Laplacian. It is shown that this improves upon the previously known bound, which depended on the degree sequence of the graph. Estimates on the new bound are provided.
A lower bound on the number of acyclic orientations of a graph is given, with the help of the probabilistic method. This argument can take advantage of structural properties of the graph: it is shown how to obtain stronger bounds for small-degree graphs of girth at least five, than are possible for arbitrary graphs. A simpler proof of the known lower bound for arbitrary graphs is also obtained.
Both the upper and lower bounds are shown to extend to the general problem of bounding the chromatic polynomial from above and below along the negative real axis.

MSC:

05C15 Coloring of graphs and hypergraphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon: The number of spanning trees in regular graphs,Random Structures & Algorithms 1 (1990), no. 2, 175-181. · Zbl 0820.05033 · doi:10.1002/rsa.3240010204
[2] N. Alon, andJ. H. Spencer:The Probabilistic Method, Wiley, 1992.
[3] N. Alon, andN. Kahale: personal communication, August 1993.
[4] J. D. Annan:A randomized approximation algorithm for counting the number of forests in dense graphs, Combinatorics, Probability and Computing3 (1994), no. 3, 273-283. · Zbl 0809.05086 · doi:10.1017/S0963548300001188
[5] N. Biggs:Algebraic Graph Theory, Cambridge University Press, 1974. · Zbl 0284.05101
[6] J. A. Bondy, andU. S. R. Murty:Graph Theory and Applications, American Elsevier, 1976. · Zbl 1226.05083
[7] H. Chernoff: A measure for asymptotic efficiency of tests of a hypothesis based on the sum of observations,Ann. Math. Statist.,23 (1952), 493-507. · Zbl 0048.11804 · doi:10.1214/aoms/1177729330
[8] P. Erd?s, andH. Sachs: Regulare Graphe gegebener Taillenweite mit minimaler Knotenzahl,Wiss. Z. Univ. Halle-Wittenberg, Math.-Nat.,12 (1963), no. 3, 251-258.
[9] W. Goddard, C. Kenyon, V. King, andL. J. Schulman:Optimal Randomized Algorithms for Local Sorting and Set-Maxima, SIAM J. Computing,22 (1993), no. 2, 272-283; Also in: Optimal Randomized Algorithms for Local Sorting and Set-Maxima, W. Goddard, V. King and L. Schulman, Proc. Twenty Second Annual ACM Symp. on Theory of Computing (1990), 45-53. · Zbl 0770.68047
[10] F. Jaeger, D. L. Vertigan, andD. J. A. Welsh: On the Computational Complexity of the Jones and Tutte Polynomials,Proceedings of the Cambridge Philosophical Society, vol.108 (1990), 35-53. · Zbl 0747.57006 · doi:10.1017/S0305004100068936
[11] R. Graham, F. Yao, andA. Yao: Information Bounds are Weak in the Shortest Distance Problem,J. ACM,27 (1980), 428-444. · Zbl 0475.68043 · doi:10.1145/322203.322206
[12] N. Kahale:Expander Graphs. PhD thesis, Massachusetts Institute of Technology, September 1993. MIT Laboratory for Computer Science, Technical Report MIT/LCS/TR-591.
[13] N. Linial: Hard enumeration problems in geometry and combinatorics,SIAM J. on Algebraic and Discrete Methods,7 (1986), 331-335. · Zbl 0596.68041 · doi:10.1137/0607036
[14] A. Lubotzky, R. Phillips, andP. Sarnak: Ramanujan graphs,Combinatorica,8 (1988), no. 3, 261-277. · Zbl 0661.05035 · doi:10.1007/BF02126799
[15] M. Marcus, andH. Minc: A Survey of Matrix Theory and Matrix Inequalities, Prindle Weber and Schmidt 1964, Dover 1992, ?II.4.1.7 114. · Zbl 0126.02404
[16] G. A. Margulis: Explicit group-theoretical constructions of combinatorial schemes and their applications to the design of expanders and concentrators,Problemy Pereda?i Informacii,24 (1988), no. 1, 51-60.
[17] B. D. McKay: Spanning trees in regular graphs,Euro. J. Combinatorics,4 (1983), 149-160. · Zbl 0517.05043
[18] U. Manber, andM. Tompa: The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem,SIAM J. Comp.,13 (1984), 109-115. · Zbl 0537.68067 · doi:10.1137/0213008
[19] R. P. Stanley:Enumerative Combinatorics, Wadsworth & Brooks/Cole, 1986.
[20] R. P. Stanley: Acyclic Orientations of Graphs,Discrete Mathematics,5 (1973), 171-178. · Zbl 0258.05113 · doi:10.1016/0012-365X(73)90108-8
[21] L. Tak?cs: On the Number of Distinct Forests,SIAM J. Discrete Math, Vol.3, No. 4, Nov. 1990, 574-581. · Zbl 0715.05035 · doi:10.1137/0403050
[22] J. S. Vitter, andP. Flajolet: Average-case analysis of algorithms and data structures, Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, MIT press (edited by J. Van Leeuwen), 1990, 433-524. · Zbl 0900.68251
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.