In this paper, we introduce and study a new scoring game on graphs called smash and grab. In this game, two players, called Left and Right, take turns removing a vertex of the graph as well as all of its neighbours that become isolated by this removal. For each player and each of their turns, they score the number of vertices that were removed on their turn. The game ends when there are no more vertices remaining, and the player with the highest final score wins. We denote by Ls(G) the difference between Left and Right's final scores in G when Left starts and both players play optimally (they both aim to maximise their scores). We mainly study this parameter for different graph classes. We notably prove that Ls(F)≥0 for any forest F (i.e., the first player cannot lose). We then use this result to compute the exact value of Ls(G) for particular forests such as unions of paths and subdivided stars. The result in paths then solves the case of a unique cycle. Finally, we prove that, for a generalisation of the game, computing the score is PSPACE-complete.

The (a,b)-monochromatic transversal game is an avoider-enforcer combinatorial game in which two players, Alice and Bob, alternately take turns colouring respectively a vertices in red and b vertices in blue of a hypergraph. She wins the game by obtaining a red transversal while he wins by obtaining a monochromatic blue hyperedge. Also, both players are enabled to start the game and they play optimally. In this paper, we analyze the game played on biclique-hypergraphs of powers of paths and of powers of cycles showing strategies that, depending on the choice of the parameters a and b, allow a specific player to win the game.

Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollak [Bell System Tech. J., 50 (1971), pp. 2495–2519] and Djoković [J. Combinatorial Theory Ser. B, 14 (1973), pp. 263–267]. Several papers followed with various characterizations of partial cubes. In this paper, it is proven that a subdivision of a complete graph of order n ($n \geq 4$) is a partial cube if and only if it is isomorphic to $S(K_n)$ or there exist $n-1$ nonsubdivided edges of $K_n$ adjacent to a common vertex in the subdivision and the other edges of $K_n$ are subdivided an odd number of times. As a corollary, we build partial cubes with arbitrary graph as a minor.

In this paper we are concerned with the so-called clique-colorations of a graph, that is, colorations of the vertices so that no maximal clique is monochromatic. On one hand, it is known to be NP-complete to decide whether a perfect graph is 2-clique-colorable, or whether a triangle-free graph is 3-clique-colorable; on the other hand, there is no example of a perfect graph where more than three colors would be necessary. We first exhibit some simple recursive methods to clique-color graphs and then relate the chromatic number, the domination number, and the maximum cardinality of a stable set to the clique-chromatic number. We show exact bounds and polynomial algorithms that find the clique-chromatic number for some classes of graphs and prove NP-completeness results for some others, trying to find the boundary between the two. For instance, while it is NP-complete to decide whether a graph of maximum degree 3 is 2-clique-colorable, K 1,3 -free graphs without an odd hole turn out to be always 2-clique-colorable by a polynomial algorithm. Finally, we show that "almost" all perfect graphs are 3-clique-colorable.