Search

The coloring game is played by Alice and Bob on a finite graph G. They take turns properly coloring the vertices with t colors. The goal of Alice is to color the input graph with t colors, and Bob does his best to prevent it. If at any point there exists an uncolored vertex without available color, then Bob wins; otherwise Alice wins. The game chromatic number χg(G) of G is the smallest number t such that Alice has a winning strategy. In 1991, Bodlaender showed the smallest tree T with χg(T) equal to 4, and in 1993 Faigle et al. proved that every tree T satisfies the upper bound χg(T)≤4. The stars T = K1,p with p ≥ 1 are the only trees satisfying χg(T) = 2; and the paths T = Pn, n ≥ 4, satisfy χg(T) = 3. Despite the vast literature in this area, there does not exist a characterization of trees with χg(T) = 3 or 4. We answer a question about the required degree to ensure χg(T) = 4, by exhibiting infinitely many trees with maximum degree 3 and game chromatic number 4. [ABSTRACT FROM AUTHOR]

A q-total coloring of G is an assignment of q colors to the vertices or edges of G, so that adjacent or incident elements have different colors. The Total Coloring Conjecture (TCC) asserts that a total coloring of a graph G has at least ∆ + 1 and at most ∆ + 2 colors. Rosenfeld has shown that the total chromatic number of a cubic graph is either 4 (Type 1) or 5 (Type 2). We present Type 1 new infinite families of snarks (cubic bridgeless graphs of chromatic index 4) obtained by the Kochol superposition of Goldberg with t-Semiblowup snarks. These results provide evidence of a negative answer for the question proposed by Cavicchioli et al. (2003) about the smallest order of a Type 2 snark of girth at least 5. [ABSTRACT FROM AUTHOR]

A biclique q-coloring is an assignment of q-colors to the vertices of a graph G, so that no biclique (maximal set of vertices that induces a complete bipartite subgraph of G with at least one edge) is monochromatic. Inspired by the coloring game, we introduce the biclique q-coloring game played on a graph G defined as follows. Two players, Alice and Bob, alternately color the vertices of a graph G using q colors. Alice's goal is to color the vertices of G so that no biclique is monochromatic, and Bob tries to prevent this. Both players play optimally and respect the following rule: if a biclique is fully colored, then there exist at least two vertices in the biclique with different colors. In this paper, we prove that the biclique q-coloring game is PSPACE-complete and study the game in powers of paths Pk n. [ABSTRACT FROM AUTHOR]

The search for counterexamples to the Four Color Conjecture originated snarks, a very special class of cubic graphs. In this paper, we consider the equitable total coloring of snarks. A total coloring is equitable if the number of elements colored with each color differs by at most one, and the least integer for which a graph has such a coloring is called its equitable total chromatic number. In 2002, Wang conjectured that the equitable total chromatic number of a graph is at most ∆ + 2, and this was proved for cubic graphs. Therefore, the equitable total chromatic number of a cubic graph is either 4 or 5. We provide evidence to a negative answer to the question proposed in 2016 about the existence of a Type 1 cubic graph with girth greater than 4 and equitable total chromatic number 5, by determining equitable 4-total colorings for every member of three infinite families of snarks with girth 5. [ABSTRACT FROM AUTHOR]

Abstract: We consider the Impartial Solitaire Clobber which is a one-player combinatorial game on graphs. The problem of determining the minimum number of remaining stones after a sequence of moves was proved to be NP-hard for graphs in general and, in particular, for grid graphs. This problem was studied for paths, cycles and trees, and it was proved that, for any arrangement of stones, this number can be computed in polinomial time. We study a more complex question related to determining the color and the location of the remaining stones. A graph G is strongly 1-reducible if: for any vertex v of G, for any arrangement of stones on G such that is non-monochromatic, and for any color c, there exists a succession of moves that yields a single stone of color c on v. We investigate this problem for powers of paths and for powers of cycles and we prove that if , then (resp. ) is strongly 1-reducible; if , then , is not strongly 1-reducible. [Copyright &y& Elsevier]

Abstract: List partitions generalize list colourings. Sandwich problems generalize recognition problems. The polynomial dichotomy (NP-complete versus polynomial) of list partition problems is solved for 4-dimensional partitions with the exception of one problem (the list stubborn problem) for which the complexity is known to be quasipolynomial. Every partition problem for 4 nonempty parts and only external constraints is known to be polynomial with the exception of one problem (the -partition problem) for which the complexity of the corresponding list problem is known to be NP-complete. The present paper considers external constraint 4 nonempty part sandwich problems. We extend the tools developed for polynomial solutions of recognition problems obtaining polynomial solutions for most corresponding sandwich versions. We extend the tools developed for NP-complete reductions of sandwich partition problems obtaining the classification into NP-complete for some external constraint 4 nonempty part sandwich problems. On the other hand and additionally, we propose a general strategy for defining polynomial reductions from the -partition problem to several external constraint 4 nonempty part sandwich problems, defining a class of -hard problems. Finally, we discuss the complexity of the Skew Partition Sandwich Problem. [Copyright &y& Elsevier]

We characterize the graphs G such that Ch(G)+Ch(&Gmacr;)=n+1, where Ch(G) is the choice number (list-chromatic number) of G and n is its number of vertices. [Copyright &y& Elsevier]