A Contribution to the Theory of Chromatic Polynomials
1954/01/01 by W. T. Tutte · 55 citations
Mathematics · Computer Science · #Graph theory and applications #Advanced Graph Theory Research
paper · pdf · doi:10.4153/cjm-1954-010-9
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\n 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\n 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
- 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
- Several extreme coefficients of the Tutte polynomial of graphs
- 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