The graph coloring game is a famous two-player game (re)introduced by Bodlaender in 1991. Given a graph G and k ϵ N , Alice and Bob alternately (starting with Alice) color an uncolored vertex with some color in {1, • • •, k] such that no two adjacent vertices receive a same color. If eventually all vertices are colored, then Alice wins and Bob wins otherwise. The game chromatic number χ g (G) is the smallest integer k such that Alice has a winning strategy with k colors in G . It has been recently (2020) shown that, given a graph G and k ϵ N, deciding whether χ g (G) ≤ k is PSPACE-complete. Surprisingly, this parameter is not well understood even in “simple” graph classes. Let P n denote the path with n ≥ 1 vertices. For instance, in the case of Cartesian grids, it is easy to show that χ g ( P m □ P n ) ≤ 5 since χ g (G) ≤ ∆ + 1 for any graph G with maximum degree ∆. However, the exact value is only known for small values of m , namely χ g (P 1 □ P n ) = 3, χ g (P 2 □ P n ) = 4 and χ g ( P 3 □ Pn ) = 4 for n ≥ 4 [Raspaud, Wu, 2009]. Here, we prove that, for every n ≥ 18, χ g ( P 4 □ P n ) = 4.

Accordingly to Duchet (1987), the first paper of convexity on general graphs, in english, is the 1981 paper “Convexity in graphs”. One of its authors, Frank Harary, introduced in 1984 the first graph convexity games, focused on the geodesic convexity, which were investigated in a sequence of five papers that ended in 2003. In this paper, we continue this research line, extend these games to other graph convexities, and obtain winning strategies and complexity results. Among them, we obtain winning strategies for general convex geometries in graphs. We also obtain the first PSPACE-hardness results on convexity games, by proving that the normal play and the misère play of the hull game on the geodesic and the monophonic convexities are PSPACE-complete.

A target set selection model is a graph G with a threshold function τ : V(G) → N upper-bounded by the vertex degree. For a given model, a set S0 ⊆ V(G) is a target set if V(G) can be partitioned into non-empty subsets S0, S1,....,St such that, for all i∈{1,....,t}, Si contains exactly every vertex v having at least τ(v) neighbors in S0∪⋯∪Si−1. We say that t is the activation time tτ(S0) of the target set S0. The problem of, given such a model, finding a target set of minimum size has been extensively studied in the literature. In this article, we investigate its variant, which we call TSS-time, in which the goal is to find a target set S0 that maximizes tτ(S0). That is, given a graph G, a threshold function τ in G, and an integer k, the objective of the TSS-time problem is to decide whether G contains a target set S0 such that tτ(S0)≥k. Let τ*=maxV∈V(G)τ(v). Our main result is the following dichotomy about the complexity of TSS-time when G belongs to a minor-closed graph class C: if C has bounded local treewidth, the problem is FPT parameterized by k and τ*; otherwise, it is NP-complete even for fixed k = 4 and τ* = 2. We also prove that, with τ = 2, the problem is NP-hard in bipartite graphs for fixed k = 5, and from previous results we observe that TSS-time is NP-hard in planar graphs and W[1]-hard parameterized by treewidth. Finally, we present a linear-time algorithm to find a target set S0 in a given tree maximizing tτ(S0).

There has been great interest in deciding whether a combinatorial structure satisfies some property, or in estimating the value of some numerical function associated with this combinatorial structure, by considering only a randomly chosen substructure of sufficiently large, but constant size. These problems are called property testing and parameter testing, where a property or parameter is said to be testable if it can be estimated accurately in this way. The algorithmic appeal is evident, as, conditional on sampling, this leads to reliable constant-time randomized estimators. Our paper addresses property testing and parameter testing for permutations in a subpermutation perspective; more precisely, we investigate permutation properties and parameters that can be well-approximated based on randomly chosen subpermutations of much smaller size. In this context, we give a permutation counterpart of a famous result by Alon and Shapira [6] stating that every hereditary graph property is testable. Moreover, we develop a theory of convergence of permutation sequences, which is used to characterize testable permutation parameters along the lines of the work of Borgs et al. [12] in the case of graphs. This theory is interesting for its own sake, as it describes the closure of the set of all permutations as a special class of Lebesgue measurable functions in [0, 1]2, which in turn may be used to define a new model of random permutations.