Eric Duchene

Nicolas Bousquet, Antoine Dailly, Eric Duchene et al.

We introduce a variant of the vertex-distinguishing edge coloring problem, where each edge is assigned a subset of colors. The label of a vertex is the union of the sets of colors on edges incident to it. In this paper we investigate the problem of finding a coloring with the minimum number of colors where every vertex receives a distinct label. Finding such a coloring generalizes several other well-known problems of vertex-distinguishing colorings in graphs.We show that for any graph (without connected component reduced to an edge or a single vertex), the minimum number of colors for which such a coloring exists can only take 3possible values depending on the order of the graph. Moreover, we provide the exact value for paths, cycles and complete binary trees.

Antoine Dailly, Eric Duchene, Urban Larsson et al.

We introduce CUT, the class of 2-player partition games. These are NIM type games, played on a finite number of heaps of beans. The rules are given by a set of positive integers, which specifies the number of allowed splits a player can perform on a single heap. In normal play, the player with the last move wins, and the famous Sprague-Grundy theory provides a solution. We prove that several rulesets have a periodic or an arithmetic periodic Sprague-Grundy sequence (i.e. they can be partitioned into a finite number of arithmetic progressions of the same common difference). This is achieved directly for some infinite classes of games, and moreover we develop a computational testing condition, demonstrated to solve a variety of additional games. Similar results have previously appeared for various classes of games of take-and-break, for example octal and hexadecimal; see e.g. Winning Ways by Berlekamp, Conway and Guy (1982). In this context, our contribution consists of a systematic study of the subclass `break-without-take'.