Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph

DOI10.1007/BF01261322zbMath0861.05027OpenAlexW2075625125MaRDI QIDQ2563513

Leonard J. Schulman, Nabil Kahale

Publication date: 4 May 1997

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01261322

zbMATH Keywords

upper boundspectrumlower boundLaplacianchromatic polynomialacyclic orientations

Mathematics Subject Classification ID

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

Related Items (10)

Some inequalities for the Tutte polynomial ⋮ Upper bound for the number of spanning forests of regular graphs ⋮ On the number of upward planar orientations of maximal planar graphs ⋮ The acyclic orientation game on random graphs ⋮ On the number of forests and connected spanning subgraphs ⋮ Acyclic orientations of random graphs ⋮ Elements of a theory of simulation. II: Sequential dynamical systems. ⋮ Exponential growth constants for spanning forests on Archimedean lattices: Values and comparisons of upper bounds ⋮ Monomial bases for broken circuit complexes ⋮ Forests, colorings and acyclic orientations of the square lattice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spanning trees in regular graphs
• Ramanujan graphs
• Acyclic orientations of graphs
• On the Number of Distinct Forests
• The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
• Hard Enumeration Problems in Geometry and Combinatorics
• Information Bounds Are Weak in the Shortest Distance Problem
• The number of spanning trees in regular graphs
• Optimal Randomized Algorithms for Local Sorting and Set-Maxima
• A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
• On the computational complexity of the Jones and Tutte polynomials
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph