We consider a graph coloring algorithm that processes vertices in order taken uniformly at random and assigns colors to them using First-Fit strategy. We show that this algorithm uses, in expectation, at most (1+o(1))⋅ln n / ln ln n different colors to color any forest with n vertices. We also construct a family of forests that shows that this bound is best possible.

We prove that seminormality of cut polytopes is equivalent to normality. This settles two conjectures regarding seminormality of cut polytopes.

A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line $$L$$ if the intersection of any member with $$L$$ is a nonempty segment. It is proved that the intersection graphs of simple families of compact arc-connected sets in the plane pierced by a common line have chromatic number bounded by a function of their clique number.

We prove that if a pure simplicial complex $$\Delta $$ of dimension $$d$$ with $$n$$ facets has the least possible number of $$(d-1)$$ -dimensional faces among all complexes with $$n$$ faces of dimension $$d$$ , then it is vertex decomposable. This answers a question of J. Herzog and T. Hibi. In fact, we prove a generalization of their theorem using combinatorial methods.

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set $$X$$ in $$\mathbb{R }^2$$ that is not an axis-aligned rectangle and for any positive integer $$k$$ produces a family $$\mathcal{F }$$ of sets, each obtained by an independent horizontal and vertical scaling and translation of $$X$$ , such that no three sets in $$\mathcal{F }$$ pairwise intersect and $$\chi (\mathcal{F })>k$$ . This provides a negative answer to a question of Gyárfás and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.