Let be a positive integer. We say that a graph is strongly -colorable if for every partition of the vertices to sets of size at most there is a proper -coloring of in which the vertices in each set of the partition have distinct colors.
Conjecture If is the maximal degree of a graph , then is strongly -colorable.
Conjecture Let be a cubic graph with no bridge. Then there is a coloring of the edges of using the edges of the Petersen graph so that any three mutually adjacent edges of map to three mutually adjancent edges in the Petersen graph.
Problem Let be an indexed family of filters on sets. Which of the below items are always pairwise equal?
1. The funcoid corresponding to this function (considered as a single argument function on indexed families) applied to the reloidal product of filters .
2. The funcoid corresponding to this function (considered as a single argument function on indexed families) applied to the starred reloidal product of filters .
Let be a graph. If and are two integers, a -colouring of is a function from to such that for each edge . Given a list assignment of , i.e.~a mapping that assigns to every vertex a set of non-negative integers, an -colouring of is a mapping such that for every . A list assignment is a --list-assignment if and for each vertex . Given such a list assignment , the graph G is --colourable if there exists a --colouring , i.e. is both a -colouring and an -colouring. For any real number , the graph is --choosable if it is --colourable for every --list-assignment . Last, is circularly -choosable if it is --choosable for any , . The circular choosability (or circular list chromatic number or circular choice number) of G is
Problem What is the best upper bound on circular choosability for planar graphs?
A nowhere-zero -flow on is an orientation of together with a function from the edge set of into the real numbers such that , for all , and . The circular flow number of is inf has a nowhere-zero -flow , and it is denoted by .
A graph with maximum vertex degree is a class 1 graph if its edge chromatic number is .
Conjecture Let be an integer and a -regular graph. If is a class 1 graph, then .
Problem Let be natural numbers with . It follows from the pigeon-hole principle that there exist distinct subsets with . Is it possible to find such a pair in polynomial time?