We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.

A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T),...

The reaping number ${𝔯}_{m,n}\left(𝔹\right)$ of a Boolean algebra $𝔹$ is defined as the minimum size of a subset $𝒜\subseteq 𝔹\setminus \left\{𝐎\right\}$ such that for each $m$-partition $𝒫$ of unity, some member of $𝒜$ meets less than $n$ elements of $𝒫$. We show that for each $𝔹$, ${𝔯}_{m,n}\left(𝔹\right)={𝔯}_{\lceil \frac{m}{n-1}\rceil ,2}\left(𝔹\right)$ as conjectured by Dow, Steprāns and Watson. The proof relies on a partition theorem for finite trees; namely that every $k$-branching tree whose maximal nodes are coloured with $\ell$ colours contains an $m$-branching subtree using at most $n$ colours if and only if $\lceil \frac{\ell }{n}\rceil <\lceil \frac{k}{m-1}\rceil$.

Word and tree codes are studied in a common framework, that of polypodes which are sets endowed with a substitution like operation. Many examples are given and basic properties are examined. The code decomposition theorem is valid in this general setup.

Word and tree codes are studied in a common framework, that of polypodes which are sets endowed with a substitution like operation. Many examples are given and basic properties are examined. The code decomposition theorem is valid in this general setup.

We consider Weil sums of binomials of the form $W_{F,d}\left(a\right)={\sum }_{x\in F}\psi (x^d-ax)$, where F is a finite field, ψ: F → ℂ is the canonical additive character, $gcd(d,|F^{\times }\left|\right)=1$, and $a\in F^{\times }$. If we fix F and d, and examine the values of $W_{F,d}\left(a\right)$ as a runs through $F^{\times }$, we always obtain at least three distinct values unless d is degenerate (a power of the characteristic of F modulo $|F^{\times }|$). Choices of F and d for which we obtain only three values are quite rare and desirable in a wide variety of applications. We show that if F is a field of order 3ⁿ with n odd, and $d=3^r+2$ with...