Colouring
Contents
Problems in this category
 Are tperfect graphs strongly tperfect?
 Berge's conjecture on path partitions
 Chromatic number of tperfect graphs
 Equitable list colouring
 Extreme direction Sperner for square 01 matrix
 List colouring of two matroids
 Minimum polychromatic number for plane graphs with fixed girth
 Partitioning a bipartite graph into proportional factors
 Skewsupermodular colouring with prescribed classsizes
 Skewsupermodular colouring with two class sizes
 Skewsupermodular list colouring
 Strong colouring of matroidgraph 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 listcolouring 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 tperfect graph 4colourable? 
List colouring
The most famous open problem about list colouring is arguably the edge list colouring conjecture. Galvin ^{[1]} 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 klistcoloured, 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 skewsupermodular extension.
Let [math]p_1[/math] and [math]p_2[/math] be integer skewsupermodular 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 klistcolourable for any [math]k \geq \Delta(G)+1[/math]? 
The equitable version of the Supermodular colouring theorem is known to be true ^{[2]}, but it is open if two different class sizes are prescribed:
Let [math]p_1[/math] and [math]p_2[/math] be integer skewsupermodular 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 kcoloring 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 PPADcomplete, but the complexity of the following polyhedral version is open:
Let A be an [math]n \times n[/math] 01 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)? 
References
 ↑ F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B 63(1) (1995), 153158. DOI link.
 ↑ A. Bernáth, T. Király, Covering skewsupermodular functions by hypergraphs of minimum total size, DOI link, EGRES Technical Report.