A Contribution to the Theory of Chromatic Polynomials
1954/01/01 by W. T. Tutte · 1,031 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Chromatic polynomial #Chromatic scale #Combinatorics #Discrete mathematics #Enumeration #Graph #Graph theory and applications #Mathematics #Planar graph #Vertex (graph theory)
paper · pdf · doi:10.4153/cjm-1954-010-9
published in Canadian Journal of Mathematics 6, 80-91 (Cambridge University Press)
openalex publication_date 1954/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
Abstract
Summary Two polynomials θ ( G, n ) and ϕ ( G, n ) connected with the colourings of a graph G or of associated maps are discussed. A result believed to be new is proved for the lesser-known polynomial ϕ ( G, n ). Attention is called to some unsolved problems concerning ϕ ( G, n ) which are natural generalizations of the Four Colour Problem from planar graphs to general graphs. A polynomial χ ( G, x, y ) in two variables x and y , which can be regarded as generalizing both θ ( G, n ) and ϕ ( G, n ) is studied. For a connected graph χ ( G, x, y ) is defined in terms of the “spanning” trees of G (which include every vertex) and in terms of a fixed enumeration of the edges.
Cited by
- Three-Bit Flows and Cycle Covers. Part I
- Nowhere-zero flows in signed graphs: A survey
- Tutte Invariants for Alternating Dimaps
- Weighted Coxeter graphs and generalized geometric representations of Coxeter Groups
- Multipath matroids, digraph colourings, and the Tutte polynomial
- Algorithm for Interpretable Graph Features via Motivic Persistent Cohomology
- Chromatic Polynomial Evaluation Spectra
- Nowhere-zero flow reconfiguration
- The ratio of the numbers of odd and even cycles in outerplanar graphs
- The Complexity of Computing the Sign of the Tutte Polynomial
- Arithmetic matroids, Tutte polynomial, and toric arrangements
- Polynomial invariants of cyclically ordered graphs
- On removable edge subsets in graphs with a nowhere-zero 4-flow
- A new edge selection heuristic for computing the Tutte polynomial of an undirected graph
- Open problems of the 33rd Workshop on Cycles and Colourings
- The magnitude of a graph
- Toric partial orders
- The Active Bijection 2.a - Decomposition of activities for matroid bases, and Tutte polynomial of a matroid in terms of beta invariants of minors
- Planar Graphs of Odd-Girth at Least 9 are Homomorphic to the Petersen Graph
- The algebra of flows in graphs
- Edge colourings and topological graph polynomials
- A quasi-tree expansion of the Krushkal polynomial
- Manhattan and Chebyshev flows
- Geometric description of d-dimensional flows of a graph
- Sublinear bounds for nullity of flows and approximating Tutte's flow conjectures
- A recursive definition for the polymatroid Tutte polynomial
- Combinatoire du polynôme de Tutte et des cartes planaires
- Tutte Polynomials of Tensor Products of Signed Graphs and their Applications in Knot Theory
- Nowhere-zero flows on signed supereulerian graphs
- Tutte Polynomial of Ideal Arrangement
- Dual matroid polytopes and internal activity of independence complexes
- On the coefficients of interior and exterior polynomials of polymatroids
- Colorings and flows on CW complexes, Tutte quasi-polynomials and arithmetic matroids
- Generalized Bijective Maps between G-Parking Functions, Spanning Trees, and the Tutte Polynomial
- Graphs on Surfaces and the Partition Function of String Theory
- Tutte polynomial, complete invariant, and theta series
- Computer-assisted graph theory: a survey
- Graph polynomials and symmetries
- Digraph Polynomials for Counting Cycles and Paths
- Chain characteristic polynomials of matroids
- Enumerative Aspects of Nullstellensatz Certificates
- A Blass-Sagan bijection on Eulerian equivalence classes
- Kauffman bracket polynomials, perfect matchings and cluster variables
- Multivariate Tutte polynomials of semimatroids
- Flows on Bidirected Graphs
- The replacements of signed graphs and Kauffman brackets of links
- A relationship between two graphical models of the Kauffman polynomial
- A survey of repositories in graph theory
- Note on the subgraph component polynomial
- On the 2-dimensional flow number of the Flower snarks
- A solution to the tennis ball problem
- Jones Polynomials and their Zeros for a Family of Knots and Links
- Distance Hereditary Graphs and the Interlace Polynomial
- Flows on flow-admissible signed graphs
- Several extreme coefficients of the Tutte polynomial of graphs
- The closure of a linear space in a product of lines
- Graph polynomials and their applications I: The Tutte polynomial
- Relative Tutte Polynomials for Colored Graphs and Virtual Knot Theory
- On the HOMFLY and Tutte polynomials
- A quasi-tree expansion for the surface Tutte polynomial
- The Tutte dichromate and Whitney homology of matroids
- Quotients of Spheres By Linear Actions of Tori
- Characteristic polynomials of semimatroids and their connections to matroids, hyperplane arrangements and graph colorings
- Flow polynomials of a signed graph
- An algorithm and new bounds for the circular flow number of snarks
- Exponentially many nowhere-zero Z3-, Z4-, and Z6-flows
- The Tutte polynomial and the automorphism group of a graph
- Many flows in the group connectivity setting
- Ehrhart polynomial and multiplicity Tutte polynomial
- Zero-sum flows for Steiner triple systems
- Computing the strong alliance polynomial of a graph
- Tutte polynomials of fan-like graphs with applications in benzenoid systems
- Orientations, lattice polytopes, and group arrangements II: Modular and integral flow polynomials of graphs
- A generalization of the Tutte polynomials
- Graph colorings, flows and arithmetic Tutte polynomial
- Signed graphs with two negative edges
- The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
- Graph-polynomials
- Computing Tutte Polynomials
- Tutte Polynomials of Symmetric Hyperplane Arrangements
- Around matrix-tree theorem
- Complex-temperature phase diagrams for theq-state Potts model on self-dual families of graphs and the nature of theq→∞limit
- Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids
- Inapproximability of the Tutte polynomial
- Flow-continuous mappings -- influence of the group
- General structural results for Potts model partition functions on lattice strips
- Multiparking Functions, Graph Searching, and the Tutte Polynomial
- Spanning trees on graphs and lattices inddimensions
- Thermal operators and cluster topology in theq-state Potts model
- Cycle equivalence of graph dynamical systems
- The Tutte polynomial of the Sierpiński and Hanoi graphs
- A Survey of the Cycle Double Cover Conjecture
- The State of the Three Color Problem
- Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations
- A Simplicial Tutte "5"-flow Conjecture
- On Edge-maps whose Inverse Preserves Flows or Tensions
- The Tutte polynomial
- On the foundations of combinatorial theory I. Theory of M�bius Functions
- Computing the Tutte polynomial of a graph of moderate size
- A β Invariant for Greedoids and Antimatroids
- The medial graph and voltage- current duality
- Snarks without Small Cycles
- Catalan, Motzkin, and Riordan numbers
- Graph Polynomials and Their Applications I: The Tutte Polynomial
- Chromatic roots are dense in the whole complex plane
- Strong Tutte Functions of Matroids and Graphs
- A Tutte polynomial for signed graphs
- Recursive families of graphs
- Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs
- Tutte's dichromate for signed graphs
- Symmetries of statistics on lattice paths between two boundaries
- Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations
- Chromatic Polynomial, Colered Jones Function and q-Binomial Counting
- Biased graphs. VII. Contrabalance and antivoltages
- Flows, View Obstructions, and the Lonely Runner
- Reducible configurations for the cycle double cover conjecture
- Fractional dynamic system simulating the growth of microbe. [europepmc]
- Tree polynomials identify a link between co-transcriptional R-loops and nascent RNA folding. [europepmc]
Related