PDFLINK |

# Coloring With a Limited Paintbox

Communicated by *Notices* Associate Editor Steven Sam

On October 23, 1852 Francis Guthrie asked his brother Frederick, a student at University College London, England, to ask his professor, Augustus De Morgan, whether four colors sufficed to color the countries of a map such that two countries sharing a border must be colored differently. De Morgan had no answer to what would become known as the four-color problem, but wrote that day to William Rowan Hamilton at Trinity College, Dublin, Ireland, saying:

Query cannot a necessity for five or more be invented…. If you retort with some very simple case which makes me out a stupid animal, I think I must do as the Sphynx did.Footnote

^{1}

Hamilton wrote back on 26 October 1852 (which MacTutor 12 wryly notes was “showing the efficiency of both himself and the postal service”) saying:

I am not likely to attempt your quaternion of colour very soon.

In fact this problem would only be solved in 1976 courtesy of Kenneth Appel, Wolfgang Haken, John Koch, and the first major computer-assisted proof. Along the way many tools were developed to resolve it, including the chromatic polynomial 3, which eventually played no role in the solution but became its own avenue of research. Over the next few pages we will explore the chromatic polynomial, its generalization called the chromatic symmetric function, and two problems that, much like the four-color problem, are straightforward to state but remain open after 25 years.

### The chromatic polynomial: A limited paint palette with an unlimited amount of paint

As we might guess from the name, the chromatic polynomial is a polynomial arising from coloring, and rather than coloring maps we will be coloring graphs. A *graph* consists of a set of *vertices* and a set of *edges* connecting the vertices. The number of edge ends meeting at a vertex is its *degree*, and two vertices connected by an edge are ,*adjacent*. The graphs of interest to us are *simple*, which means

the number of vertices is finite;

no pair of vertices has more than one edge connecting them (no

*multiple edges*);no vertex has an edge connecting it to itself (no

*loops*).

We say a graph is *connected* if every pair of vertices has at least one sequence of edges connecting them, and *disconnected* otherwise. Three famous graph families that will be useful to us later are the following, examples of which can be seen in Figure 2.

- Complete graphs
The

*complete graph*has , vertices, each pair of which are adjacent.- Trees
A connected graph is a

*tree*if every pair of vertices has exactly one sequence of edges connecting them.- Path graphs
The

*path graph*has , vertices and is the tree with 2 vertices of degree 1, and vertices of degree 2 for and , .

A *proper coloring* with , colors, of a graph is a function

such that if are adjacent, then :

.

With this in mind, the *chromatic polynomial* of a graph is the number of proper colorings of the vertices of with colors.

For example, let us color the vertices of with colors. For our first vertex we have colors to choose from. Then since all our vertices are adjacent, by definition, for the second vertex we only have colors to choose from, for the third vertex we only have colors to choose from, and so on until for the vertex we only have -th colors to choose from. Hence the total number of proper colorings of the vertices of with colors is

As a second example, let us color the vertices of any tree that has vertices with colors. Choose a vertex, any vertex. For it we have colors to choose from. For all the vertices adjacent to it we have colors to choose from. For all the vertices adjacent to those we have colors to choose from, and for all the vertices adjacent to those we have colors to choose from, and so on. We note that since every pair of vertices has exactly one sequence of edges connecting them, by definition, we will only have one opportunity to color each vertex using our greedy algorithm, and when we do we will have colors to choose from after we color the first vertex. Hence the total number of proper colorings of the vertices of with colors is

As we can see from these examples, the chromatic polynomial is in fact a polynomial, even though this may not seem immediate from the definition. Lastly, returning to the motivation for its definition, Birkhoff 3 had been hoping to solve the four-color problem by showing that whenever was a *planar* graph, namely a graph that can be drawn in the plane without edges crossing.

### The chromatic symmetric function: An unlimited paint palette with a limited amount of paint

In order to describe our main protagonist we need to consider commuting variables , … and extend our proper colorings from , colors to infinitely many colors, so that now a proper coloring of a graph is a function

such that if are adjacent, then However, we must not be misled by the infinite paint palette, because if we have a graph . with vertices, then there is as much information contained in a paintbox with colors as there is in a paintbox with infinitely many colors. Instead the crucial enhancement is that while tells us the number of proper colorings with colors for all , defined below will tell us the more refined information of how many times each color is used. Moreover, because we can package all this information into a single symmetric function, as we will see, we can bring to bear the deep, extensive, and well-developed theory of symmetric functions. Thus let us define the chromatic symmetric function, which was introduced in 1995 by Richard Stanley 16 as a generalization of the chromatic polynomial and has been a rich avenue of research ever since. A symmetric function is one where permuting the indices fixes the function, and so our chromatic symmetric function defined below is indeed a symmetric function because permuting the colors fixes the function.

For example, let us color in Figure 2. Since every pair of vertices is adjacent, so will need different colors for a proper coloring, this means that all four vertices will need a different color

that can be permuted and hence, omitting details of the calculation,

As a second example, let us color the two trees in Figure 2, and Note that we can always color the vertices four different colors, so again terms such as . will arise in both cases. However, if we try to color the vertices in only two colors, then in we can color at most two vertices the same color

that can be swapped and hence, omitting details of the calculation,

In contrast, in we can color three vertices the same color

that can be swapped and hence, omitting details of the calculation,

In his paper, Stanley noted that if and then , so the chromatic symmetric function naturally generalizes the chromatic polynomial. For example, it is well known that if we evaluate , then we obtain the number of acyclic orientations of up to a sign 15, where an acyclic orientation is a placement of directions on the edges of in such a way that following the directions never leads to us going round in a cycle. With this in mind, when written as a sum of elementary symmetric functions, which we will meet later, refines this result by determining the number of acyclic orientations of , with sinks, where a sink is a vertex whose incident edges are all directed towards and we look at the coefficients of those elementary symmetric functions whose indices have , parts. This result can in turn be further refined, but that is a story for another time 1. However, there is one particular way in which and seem to differ, which leads us to our first open problem.

### Distinguishing trees

Given a hydrocarbon, how many isomers are there? Isomers have the same chemical formula but different configurations, so equivalently how many different configurations can , have? This problem remains open to this day.

However, we note that if we omit the hydrogens in the butane isomers, then we have two trees. In fact, they are and from earlier. This is true in general: if we omit the hydrogens, then we obtain a tree. So one way to distinguish hydrocarbons would be to know when two trees are the same, or isomorphic. Informally two graphs are isomorphic if we can redraw one so it is the other. More formally, two graphs and are *isomorphic* if and only if there exists a 1-1 correspondence

such that if are adjacent in then , are adjacent in In practice it is often easier to prove that two graphs are not isomorphic by finding a trait or .*invariant* that differs, such as the number of vertices or edges. For example, and are not isomorphic because has vertices of degree 2 whereas does not. However, they both have the same chromatic polynomial, so the chromatic polynomial is an example of an invariant that cannot be used to prove that , and are not isomorphic. From earlier we know that every tree on vertices has chromatic polynomial so it can never be used to distinguish non-isomorphic trees with the same number of vertices. However, when we calculated the chromatic symmetric functions of , and we saw that

so the chromatic symmetric function could be used to distinguish non-isomorphic trees. This was proposed by Stanley 16, and is now known as Stanley’s tree problem, which we will formulate below as a conjecture to prove.

This has been verified for all trees with up to 29 vertices 10, and has been proved for only a few families of trees:

- Spiders 13
A

*spider*is a tree consisting of disjoint path graphs and a central vertex joined to a degree 1 vertex in each path graph.

For example,

is both a spider and a caterpillar.

### A positive outlook

For our second open problem we need to introduce the space that chromatic symmetric functions live in, the algebra of symmetric functions. The algebra of symmetric functions, is a subalgebra of , generated by the * elementary symmetric functions -th* for

for instance and that ,

and is freely generated by the is known as the *fundamental theorem of symmetric functions*. A basis for is given by all *elementary symmetric functions*

where is a list of weakly decreasing positive integers, for instance and we say that any , is * -positive* if it can be written as a positive linear combination of elementary symmetric functions, and is of interest due to its connection to permutation representations. For example,

is not and -positive, is the smallest graph whose chromatic symmetric function is not However, -positive.

is More generally, we can see that -positive.

where because each vertex must be colored a different color, and hence each proper coloring gives a monomial

where all the indices are different. Also the colors of a given proper coloring can be permuted in different ways, and each gives a valid proper coloring. Hence

The complete graphs are a special case of a family of graphs called unit interval graphs. A *unit interval graph* on vertices is formed as follows. Choose a collection of intervals such that no interval contains another. Then has vertices labeled and an edge between vertices if for some For example, let . be a graph on 4 vertices. If then , and if , then , However, . for any This leads us to our second open problem that was originally posed as a conjecture by Richard Stanley and John Stembridge in 1993 in terms of partially ordered sets not containing a chain of three elements and one further element incomparable to the chain. While the conjecture’s name still bears this terminology, it is easiest for us to state it using unit interval graphs, a reduction that is due to Mathieu Guay-Paquet .9.

**Table 1.**

Data on and trees. -positivity

Number of vertices, | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |

Number of trees, | 1 | 1 | 1 | 2 | 3 | 6 | 11 | 23 | 47 | 106 | 235 | 551 | 1301 |

is -positive | 1 | 1 | 1 | 1 | 2 | 1 | 3 | 1 | 2 | 2 | 5 | 1 | 4 |

Like Stanley’s tree problem, this conjecture has been proved for only a few families, for example considering graphs on vertices we have

Complete graphs, namely ;

Path graphs, namely 16;

Complements of triangle-free graphs, namely 17;

namely -chains, and 8;

Triangular ladders, namely 5.

In particular, a number of these and other results have been proved using generalizations of the chromatic symmetric function to quasisymmetric functions 14 or to symmetric functions in noncommuting variables 8. Furthermore, through the generalization to quasisymmetric functions, chromatic symmetric functions of unit interval graphs have been shown to encode the decomposition into irreducible representations of a symmetric group action on the cohomology of regular semisimple Hessenberg varieties, for example 4.

One thing we can observe from the definition of unit interval graphs is that they can be thought of as a collection of complete graphs that have been lined up in a row and then squashed together. Looking individually at each complete graph we notice that it does not contain as an *induced subgraph* (a subset of vertices together with all edges connecting them). This led Stanley to widen his conjecture to propose that the chromatic symmetric function of all graphs that do not contain as a *contraction* (shrinking edges and identifying vertices) are This conjecture was recently shown to be false by Samantha Dahlberg, Angèle Foley and the author -positive.6 who proved there exist infinite families of graphs that satisfy every combination of

they contain as an induced subgraph;

they contain as a contraction;

their chromatic symmetric functions are -positive.

Some of these can be seen in Figure 4.

Now that we have met these two famed open problems on chromatic symmetric functions, it is time to tie these two research threads together and end with one final open problem. From our discussion on the conjecture we see that the chromatic symmetric function of the tree -free is not although that of the path graph -positive, is. So a natural question to ask is when is the chromatic symmetric function of a tree The data computed so far by Samantha Dahlberg, Adrian She and the author -positive?7 in Table 1 implies the answer is not often beyond the chromatic symmetric function of the path graphs, and their conjecture is our final open problem, which has been confirmed by Kai Zheng 20 for degree .

## Acknowledgments

The author would like to thank the referees, Farid Aliniaeifard, Niall Christie, Sheila Sundaram, and Victor Wang for helpful suggestions, and especially Richard Stanley whose suggestions, insights, and stories made writing and researching this article all the more chromatic.

## References

- [1]
- F. Aliniaeifard, V. Wang, and S. van Willigenburg,
*The chromatic symmetric function of a graph centred at a vertex*, arXiv:2108.04850v1, 2021. - [2]
- José Aliste-Prieto and José Zamora,
*Proper caterpillars are distinguished by their chromatic symmetric function*, Discrete Math.**315**(2014), 158–164, DOI 10.1016/j.disc.2013.10.016. MR3130368Show rawAMSref`\bib{Jose2}{article}{ author={Aliste-Prieto, Jos\'{e}}, author={Zamora, Jos\'{e}}, title={Proper caterpillars are distinguished by their chromatic symmetric function}, journal={Discrete Math.}, volume={315}, date={2014}, pages={158--164}, issn={0012-365X}, review={\MR {3130368}}, doi={10.1016/j.disc.2013.10.016}, }`

Close amsref.^{✖} - [3]
- George D. Birkhoff,
*A determinant formula for the number of ways of coloring a map*, Ann. of Math. (2)**14**(1912/13), no. 1-4, 42–46, DOI 10.2307/1967597. MR1502436Show rawAMSref`\bib{Birk}{article}{ author={Birkhoff, George D.}, title={A determinant formula for the number of ways of coloring a map}, journal={Ann. of Math. (2)}, volume={14}, date={1912/13}, number={1-4}, pages={42--46}, issn={0003-486X}, review={\MR {1502436}}, doi={10.2307/1967597}, }`

Close amsref.^{✖} - [4]
- Patrick Brosnan and Timothy Y. Chow,
*Unit interval orders and the dot action on the cohomology of regular semisimple Hessenberg varieties*, Adv. Math.**329**(2018), 955–1001, DOI 10.1016/j.aim.2018.02.020. MR3783432Show rawAMSref`\bib{BrosnanChow}{article}{ author={Brosnan, Patrick}, author={Chow, Timothy Y.}, title={Unit interval orders and the dot action on the cohomology of regular semisimple Hessenberg varieties}, journal={Adv. Math.}, volume={329}, date={2018}, pages={955--1001}, issn={0001-8708}, review={\MR {3783432}}, doi={10.1016/j.aim.2018.02.020}, }`

Close amsref.^{✖} - [5]
- S. Dahlberg,
*Triangular ladders are -positive*, arXiv:1811.04885v1, 2018. - [6]
- Samantha Dahlberg, Angèle Foley, and Stephanie van Willigenburg,
*Resolving Stanley’s of claw-contractible-free graphs -positivity*, J. Eur. Math. Soc. (JEMS)**22**(2020), no. 8, 2673–2696, DOI 10.4171/JEMS/974. MR4118618Show rawAMSref`\bib{DFvW}{article}{ author={Dahlberg, Samantha}, author={Foley, Ang\`ele}, author={van Willigenburg, Stephanie}, title={Resolving Stanley's $e$-positivity of claw-contractible-free graphs}, journal={J. Eur. Math. Soc. (JEMS)}, volume={22}, date={2020}, number={8}, pages={2673--2696}, issn={1435-9855}, review={\MR {4118618}}, doi={10.4171/JEMS/974}, }`

Close amsref.^{✖} - [7]
- Samantha Dahlberg, Adrian She, and Stephanie van Willigenburg,
*Schur and of trees and cut vertices -positivity*, Electron. J. Combin.**27**(2020), no. 1, Paper No. 1.2, 22. MR4057182Show rawAMSref`\bib{DShevW}{article}{ author={Dahlberg, Samantha}, author={She, Adrian}, author={van Willigenburg, Stephanie}, title={Schur and $e$-positivity of trees and cut vertices}, journal={Electron. J. Combin.}, volume={27}, date={2020}, number={1}, pages={Paper No. 1.2, 22}, review={\MR {4057182}}, }`

Close amsref.^{✖} - [8]
- David D. Gebhard and Bruce E. Sagan,
*A chromatic symmetric function in noncommuting variables*, J. Algebraic Combin.**13**(2001), no. 3, 227–255, DOI 10.1023/A:1011258714032. MR1836903Show rawAMSref`\bib{GebSag}{article}{ author={Gebhard, David D.}, author={Sagan, Bruce E.}, title={A chromatic symmetric function in noncommuting variables}, journal={J. Algebraic Combin.}, volume={13}, date={2001}, number={3}, pages={227--255}, issn={0925-9899}, review={\MR {1836903}}, doi={10.1023/A:1011258714032}, }`

Close amsref.^{✖} - [9]
- M. Guay-Paquet,
*A modular relation for the chromatic symmetric functions of posets -free*, arXiv:1306.2400v1, 2013. - [10]
- S. Heil and C. Ji,
*On an algorithm for comparing the chromatic symmetric functions of trees*, Australas. J. Combin.**75**(2019), 210–222. MR4008247Show rawAMSref`\bib{HeilJi}{article}{ author={Heil, S.}, author={Ji, C.}, title={On an algorithm for comparing the chromatic symmetric functions of trees}, journal={Australas. J. Combin.}, volume={75}, date={2019}, pages={210--222}, issn={1034-4942}, review={\MR {4008247}}, }`

Close amsref.^{✖} - [11]
- Martin Loebl and Jean-Sébastien Sereni,
*Isomorphism of weighted trees and Stanley’s isomorphism conjecture for caterpillars*, Ann. Inst. Henri Poincaré D**6**(2019), no. 3, 357–384, DOI 10.4171/AIHPD/74. MR4002670Show rawAMSref`\bib{LS}{article}{ author={Loebl, Martin}, author={Sereni, Jean-S\'{e}bastien}, title={Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars}, journal={Ann. Inst. Henri Poincar\'{e} D}, volume={6}, date={2019}, number={3}, pages={357--384}, issn={2308-5827}, review={\MR {4002670}}, doi={10.4171/AIHPD/74}, }`

Close amsref.^{✖} - [12]
- MacTutor, The four colour theorem, https://mathshistory.st-andrews.ac.uk/HistTopics/The_four_colour_theorem/.
- [13]
- Jeremy L. Martin, Matthew Morin, and Jennifer D. Wagner,
*On distinguishing trees by their chromatic symmetric functions*, J. Combin. Theory Ser. A**115**(2008), no. 2, 237–253, DOI 10.1016/j.jcta.2007.05.008. MR2382514Show rawAMSref`\bib{MMW}{article}{ author={Martin, Jeremy L.}, author={Morin, Matthew}, author={Wagner, Jennifer D.}, title={On distinguishing trees by their chromatic symmetric functions}, journal={J. Combin. Theory Ser. A}, volume={115}, date={2008}, number={2}, pages={237--253}, issn={0097-3165}, review={\MR {2382514}}, doi={10.1016/j.jcta.2007.05.008}, }`

Close amsref.^{✖} - [14]
- John Shareshian and Michelle L. Wachs,
*Chromatic quasisymmetric functions*, Adv. Math.**295**(2016), 497–551, DOI 10.1016/j.aim.2015.12.018. MR3488041Show rawAMSref`\bib{SW}{article}{ author={Shareshian, John}, author={Wachs, Michelle L.}, title={Chromatic quasisymmetric functions}, journal={Adv. Math.}, volume={295}, date={2016}, pages={497--551}, issn={0001-8708}, review={\MR {3488041}}, doi={10.1016/j.aim.2015.12.018}, }`

Close amsref.^{✖} - [15]
- Richard P. Stanley,
*Acyclic orientations of graphs*, Discrete Math.**5**(1973), 171–178, DOI 10.1016/0012-365X(73)90108-8. MR317988Show rawAMSref`\bib{StanAcyc}{article}{ author={Stanley, Richard P.}, title={Acyclic orientations of graphs}, journal={Discrete Math.}, volume={5}, date={1973}, pages={171--178}, issn={0012-365X}, review={\MR {317988}}, doi={10.1016/0012-365X(73)90108-8}, }`

Close amsref.^{✖} - [16]
- Richard P. Stanley,
*A symmetric function generalization of the chromatic polynomial of a graph*, Adv. Math.**111**(1995), no. 1, 166–194, DOI 10.1006/aima.1995.1020. MR1317387Show rawAMSref`\bib{Stan95}{article}{ author={Stanley, Richard P.}, title={A symmetric function generalization of the chromatic polynomial of a graph}, journal={Adv. Math.}, volume={111}, date={1995}, number={1}, pages={166--194}, issn={0001-8708}, review={\MR {1317387}}, doi={10.1006/aima.1995.1020}, }`

Close amsref.^{✖} - [17]
- Richard P. Stanley and John R. Stembridge,
*On immanants of Jacobi-Trudi matrices and permutations with restricted position*, J. Combin. Theory Ser. A**62**(1993), no. 2, 261–279, DOI 10.1016/0097-3165(93)90048-D. MR1207737Show rawAMSref`\bib{StanStem}{article}{ author={Stanley, Richard P.}, author={Stembridge, John R.}, title={On immanants of Jacobi-Trudi matrices and permutations with restricted position}, journal={J. Combin. Theory Ser. A}, volume={62}, date={1993}, number={2}, pages={261--279}, issn={0097-3165}, review={\MR {1207737}}, doi={10.1016/0097-3165(93)90048-D}, }`

Close amsref.^{✖} - [18]
- Wikimedia Commons, https://commons.wikimedia.org/wiki/File:DeMorganFourColour.png.
- [19]
- Wikimedia Commons, https://commons.wikimedia.org/wiki/File:CNX_Chem_20_01_butaneIsom_img.png.
- [20]
- K. Zheng,
*On the of trees and spiders -positivity*, arXiv:2008.05038v2, 2020.

## Credits

Opening image is courtesy of bgblue via Getty.

Figure 1 is courtesy of Wikimedia Commons.

Figure 3 is courtesy of OpenStax. Licensed under Creative Commons Attribution 4.0 International.

All other figures are courtesy of the author.

Photo of Stephanie van Willigenburg is by Niall Christie.