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.

Consider a graph $G=(V,E)$ of minimum degree $\delta$ and order $n$. Its irregularity strength is the smallest integer $k$ for which one can find a weighting $w:E\to \{1,2,\ldots,k\}$ such that $\sum_{e\ni u}w(e) \neq \sum_{e\ni v}w(e)$ for every pair $u,v$ of vertices of $G$. In other words, it is just the maximum edge multiplicity required in an irregular multigraph whose underlying graph is $G$. We prove that the irregularity strength of graphs with $\delta\geq n^{0.5}\ln n$ is bounded from above by $(4+o(1))\frac{n}{\delta}+4$. Our approach is based on a random ordering of the vertices of a graph suitable for applying a development of the algorithm used by Kalkowski, Karoński, and Pfender to prove the bound of $6\left\lceil\frac{n}{\delta}\right\rceil$ for $\delta\geq 1$, which is the best upper bound thus far.

Consider a simple graph $G=(V,E)$ and its proper edge coloring $c$ with the elements of the set $\{1,2,\ldots,k\}$ (or any other $k$-element set of real numbers). We say that $c$ is neighbor sum distinguishing if $\sum_{w\in N_G(v)}c(wv)\neq \sum_{w\in N_G(u)}c(wu)$ for every edge $uv\in E$. We show that such a coloring exists for any graph $G$ containing no isolated edges if $k\geq 2\Delta(G)+{\rm col}(G)-1$. The proof of this fact is based on iterative applications of the Combinatorial Nullstellensatz. As a consequence, the same number of colors is also sufficient in the well-known corresponding problem, where instead of the sums, we wish to distinguish the sets of colors met by adjacent vertices. In fact we consider list versions of both concepts and prove our assertion in this more general setting.

Let G be a simple graph of order n with no isolated edges and at most one isolated vertex. For a positive integer w, a w-weighting of G is a function $f:E(G)\rightarrow\{1,2,\dots,w\}$. An irregularity strength of G, $s(G)$, is the smallest w such that there is a w-weighting of G for which $\sum_{e:u\in e}f(e)\neq\sum_{e:v\in e}f(e)$ for all pairs of different vertices $u,v\in V(G)$. We prove that $s(G)<112\frac{n}{\delta}+28$, where $\delta$ is the minimum degree of G. For d-regular graphs, we strengthen this to $s(G)<40\frac{n}{d}+11$. These upper bounds represent improvements of many existing ones. Similar results concerning the “total” version of the irregularity strength are also discussed.