Colouring

Problems in this category

• Are t-perfect graphs strongly t-perfect?
• Berge's conjecture on path partitions
• Chromatic number of t-perfect graphs
• Equitable list colouring
• Extreme direction Sperner for square 0-1 matrix
• List colouring of two matroids
• Minimum polychromatic number for plane graphs with fixed girth
• Partitioning a bipartite graph into proportional factors
• Skew-supermodular colouring with prescribed class-sizes
• Skew-supermodular colouring with two class sizes
• Skew-supermodular list colouring
• Strong colouring of matroid-graph pairs
• Weighted bipartite edge colouring

Introduction

In graph theory, the term colouring usually refers to problems about the chromatic number of graphs and various related parameters like the list-colouring number. An extensive collection of open questions in this area can be found in the Open Problem Garden. Here we consider only a few select problems, but we extend the questions to more general stuctures, like matroids and polyhedra. Let us begin however with a purely graph theoretic question about the chromatic number:

Is every t-perfect graph 4-colourable?

List colouring

The most famous open problem about list colouring is arguably the edge list colouring conjecture. Galvin proved the bipartite case, but not much progress has been made for the general case. It is open whether Galvin's result can be extended to matroid intersection:

Given some matroids on the same ground set [math]S[/math], a colouring of [math]S[/math] is called proper if each monochromatic set is independent in each matroid. Let [math]M_1[/math] and [math]M_2[/math] be two matroids on ground set [math]S[/math], and suppose that there is a proper colouring by [math]k[/math] colours. Is it true that [math]M_1[/math] and [math]M_2[/math] can be k-list-coloured, i.e. for arbitrary lists [math]L_s[/math] of k colours for each [math]s \in S[/math], there is a proper colouring that uses colours from these lists?

Another way to extend Galvin's theorem would be to prove a list colouring version of Schrijver's Supermodular colouring theorem, or its skew-supermodular extension.

Let [math]p_1[/math] and [math]p_2[/math] be integer skew-supermodular set functions on ground set S such that [math]\max\{p_1(X),p_2(X)\}\leq \min\{|X|,k\}[/math] for every [math]X \subseteq S[/math], and for every [math]s \in S[/math] let [math]L_s[/math] be a list of k distinct positive integers. Is it true that there is a partition [math]\{Y_1,\dots,Y_l\}[/math] of S such that [math]i \in L_s[/math] for every [math]s \in Y_i[/math] (i=1,...,l), and [math]|\{i: Y_i \cap X \neq \emptyset\}| \geq \max\{p_1(X), p_2(X)\}[/math] for every [math]X \subseteq S[/math]?

Colouring with prescribed class sizes

We obtain a new class of problems if we add restrictions on the sizes of colour classes. In particular, we may require the colouring to be equitable, i.e. all colour classes have almost the same size. The list colouring version leads to the following open problem:

Is it true that every graph G is equitably k-list-colourable for any [math]k \geq \Delta(G)+1[/math]?

The equitable version of the Supermodular colouring theorem is known to be true , but it is open if two different class sizes are prescribed:

Let [math]p_1[/math] and [math]p_2[/math] be integer skew-supermodular set functions on ground set S such that [math]\max\{p_1(X),p_2(X)\}\leq \min\{|X|,k\}[/math] for every [math]X \subseteq S[/math], and let [math]m_1,m_2,n_1,n_2[/math] be positive integers such that [math]m_1 n_1+m_2 n_2=|S|[/math]. Can we decide in polynomial time if there is a partition [math]{\mathcal P}[/math] of S with [math]m_1[/math] classes of size [math]n_1[/math] and [math]m_2[/math] classes of size [math]n_2[/math], such that [math]|\{Y \in {\mathcal P}: Y \cap X \neq \emptyset\}| \geq \max\{p_1(X), p_2(X)\}[/math] for every [math]X \subseteq S[/math]?

Polychromatic colouring

A different kind of colouring problem for plane graphs is when we require each face to contain every colour. Clearly this is possible only if the number of colours is at most the length of the shortest face. Thus we can ask the following.

For a plane graph [math]G[/math], let [math]g(G)[/math] denote the length of the shortest face in [math]G[/math]. For a (not necessarily proper) [math]k[/math]-coloring of [math]V(G)[/math] we say that a face is polychromatic if all [math]k[/math] colors appear on its vertices. A k-coloring of [math]V(G)[/math] is called polychromatic if every face of [math]G[/math] is polychromatic. The polychromatic number of [math]G[/math], denoted by [math]p(G)[/math], is the largest number [math]k[/math] such that there is a polychromatic [math]k[/math]-coloring of [math]V(G)[/math]. Define [math]p(g)=\min\{p(G)|g(G)=g\}[/math]. Determine [math]p(g)[/math] exactly for every positive integer [math]g[/math]. The first open case is [math]g=5[/math] where we know that [math]2 \leq p(5) \leq 4[/math].

Various versions of Sperner's Lemma can also be interpreted as theorems on the existence of a polychromatic facet or vertex in certain coloured structures. In general, the computational version of Sperner's Lemma is PPAD-complete, but the complexity of the following polyhedral version is open:

Let A be an [math]n \times n[/math] 0-1 matrix, and suppose that the facets of the polyhedron [math]P=\{x: A x \leq {\mathbf 1},\ x \leq {\mathbf 1}\} [/math] are coloured by [math]n[/math] colours such that a facet with extreme direction [math]-e_i[/math] does not get colour [math]i[/math], and every colour appears twice. Can we find in polynomial time a vertex that is incident to facets of every colour (a panchromatic vertex)?