Matpic
mathematics, in pictures
Concept

Chromatic polynomial

The polynomial that counts, for each number of colours k, the ways to colour a graph's vertices so that neighbours differ. It is a relative of the forest and spanning-tree counts, and its coefficients obey inequalities that took decades to prove.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Counting the colourings, by deleting and contracting. A graph beside the two smaller graphs its edge deletion and contraction produce, with the number of proper colourings of each at every number of colours up to 5.

Counting the colourings

Asking whether a graph can be coloured with four colours gives a yes or a no. Asking how many ways there are gives a polynomial — and the polynomial answers the first question, and several others nobody asked.

discrete · Graph colouring The forests of a complete graph on four points. K4 forests by size: 1, 6, 15, 16; ratios 2.4000, 2.3438.

The forests a graph can hold

Count the sets of edges in a graph that contain no cycle, sorted by size, and the counts rise and fall in a single peak — more sharply peaked, John Mason conjectured in 1972, than the binomial coefficients with the same number of edges. On every graph with up to six points the strongest of his three inequalities holds, with equality exactly where cycles are too long to matter; on random graphs with nine points it holds with a margin of about one per cent. It was proved for every graph, and every matroid, in 2018.

discrete · Generating functions

Named alongside it

The objects these essays reach for when they reach for this one.

Cayleys formulaChromatic numberCountingDeletion contractionExhaustive searchGenerating functionGraph colouringLog-concavityPolynomialReal rooted polynomialRecurrence relationSpanning tree

All concepts