Occupancy fraction, fractional colouring, and triangle fraction.

Given , there exists such that, if , then for any graph on vertices of maximum degree in which the neighbourhood of every vertex in spans at most edges, (i)an independent set of drawn uniformly at random has at least vertices in expectation, and(ii)the fractional chromatic number of is at most . These bounds cannot in general be improved by more than a factor 2 asymptotically. One may view these as stronger versions of results of Ajtai, Komlós and Szemerédi and Shearer.

Single-conflict colouring.

Given a multigraph, suppose that each vertex is given a local assignment of colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no edge has both of its local colours chosen. The least for which this is always possible given any set of local assignments we call the of the graph.

Coloring triangle-free graphs with local list sizes.

We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow-up work of Bernshteyn) on the (list) chromatic number of triangle-free graphs. In both our results, we permit the amount of color made available to vertices of lower degree to be accordingly lower. One result concerns list coloring and correspondence coloring, while the other concerns fractional coloring.