Reverse Mathematics and Grundy colorings of graphs

The relationship of Grundy and chromatic numbers of graphs in the context of Reverse Mathematics is investi‐gated (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A variant of Nim

We discuss a version of Nim in which players are allowed to use a move from the traditional form of Nim or to split a pile after adding some predetermined number $q$ of coins to the pile. When $q$ is odd or negative, the play proceeds as in regular Nim. For $q$ even and non-negative, we find three patterns: $q=0$, $q=2$ and $q?4$.     

Grundy number and products of graphs

The Grundy number of a graph G, denoted by Γ(G), is the largest k such that G has a greedyk-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this paper, we study the Grundy number of the lexicographic and cartesian products of two graphs in terms of the Grundy numbers of these graphs.Regarding the lexicographic product, we show that Γ(G)×Γ(H)≤Γ(G[H])≤2^Γ(G)−1(Γ(H)−1)+Γ(G). In addition, we show that if G is a tree or Γ(G)=Δ(G)+1, then Γ(G[H])=Γ(G)×Γ(H). We then deduce that for every fixed c≥1, given a graph G, it is CoNP-Complete to decide if Γ(G)≤c×χ(G) and it is CoNP-Complete to decide if Γ(G)≤c×ω(G).Regarding the cartesian product, we show that there is no upper bound of Γ(G□H) as a function of Γ(G) and Γ(H). Nevertheless, we prove that Γ(G□H)≤Δ(G)⋅2^Γ(H)−1+Γ(H).     

Inequalities for the Grundy chromatic number of graphs

The Grundy (or First-Fit) chromatic number of a graph G is the maximum number of colors used by the First-Fit coloring of the graph G. In this paper we give upper bounds for the Grundy number of graphs in terms of vertex degrees, girth, clique partition number and for the line graphs. Next we show that if the Grundy number of a graph is large enough then the graph contains a subgraph of prescribed large girth and Grundy number.     

New Bounds on the Grundy Number of Products of Graphs

The Grundy number of a graph G is the largest k such that G has a greedy k‐coloring, that is, a coloring with k colors obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this article, we give new bounds on the Grundy number of the product of two graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:78–88, 2012     

Results on the Grundy chromatic number of graphs

Given a graph G, by a Grundy k-coloring of G we mean any proper k-vertex coloring of G such that for each two colors i and j, i<j, every vertex of G colored by j has a neighbor with color i. The maximum k for which there exists a Grundy k-coloring is denoted by Γ(G) and called Grundy (chromatic) number of G. We first discuss the fixed-parameter complexity of determining Γ(G)?k, for any fixed integer k and show that it is a polynomial time problem. But in general, Grundy number is an NP-complete problem. We show that it is NP-complete even for the complement of bipartite graphs and describe the Grundy number of these graphs in terms of the minimum edge dominating number of their complements. Next we obtain some additive Nordhaus-Gaddum-type inequalities concerning Γ(G) and Γ(G^c), for a few family of graphs. We introduce well-colored graphs, which are graphs G for which applying every greedy coloring results in a coloring of G with χ(G) colors. Equivalently G is well colored if Γ(G)=χ(G). We prove that the recognition problem of well-colored graphs is a coNP-complete problem.     

On the length of L-Grundy sequences

An L-sequence of a graph $G$ is a sequence of distinct vertices $S=(v_1,\dots ,v_k)$ such that $N\left[v_i\right]\setminus {\cup }_{j=1}^{i-1}N\left(v_j\right)\ne 0̸$. The length of a longest L-sequence is called the L-Grundy domination number, denoted ${\gamma }_{gr}^L\left(G\right)$. In this paper, we prove ${\gamma }_{gr}^L\left(G\right)\le n\left(G\right)-\delta \left(G\right)+1$, which was conjectured by Brešar, Gologranc, Henning, and Kos. We also prove some initial results about characteristics of $n$-vertex graphs satisfying ${\gamma }_{gr}^L\left(G\right)=n$.     

The Sprague–Grundy function of the real game Euclid

The game Euclid, introduced and named by Cole and Davie, is played with a pair of nonnegative integers. The two players move alternately, each subtracting a positive integer multiple of one of the integers from the other integer without making the result negative. The player who reduces one of the integers to zero wins. Unfortunately, the name Euclid has also been used for a subtle variation of this game due to Grossman in which the game stops when the two entries are equal. For that game, Straffin showed that the losing positions (a,b) with a<b are precisely the same as those for Cole and Davie’s game. Nevertheless, the Sprague–Grundy functions are not the same for the two games. We give an explicit formula for the Sprague–Grundy function for the original game of Euclid and we explain how the Sprague–Grundy functions of the two games are related.