An equitable coloring of a graph G is a proper vertex coloring of G such that the sizes of any two color classes differ by at most one. In the paper, we pose a conjecture that offers a gap-one bound for the smallest number of colors needed to equitably color every block graph. In other words, the difference between the upper and the lower bounds of our conjecture is at most one. Thus, in some sense, the situation is similar to that of chromatic index, where we have the classical theorem of Vizing and the Andersen–Goldberg–Seymour conjecture for multigraphs. The results obtained in the paper support our conjecture. More precisely, we verify it in the class of block graphs in which each vertex belongs to a maximum independent set. We also show that the conjecture is true for block graphs which contain a vertex that does not lie in an independent set of size larger than two. Finally, we verify the conjecture for some symmetric-like block graphs. In order to derive our results we obtain structural characterizations of block graphs from these classes.

Consider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colors it red or blue. Builder wins by creating either a red copy of G or a blue copy of H for some fixed graphs G and H. The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the on-line Ramsey number r̃(G,H). In this paper, we prove some new general lower and upper bounds for on-line Ramsey numbers r̃(C3,Pk) and r̃(C4,Pk).

A signed graph is a pair (G,σ), where G=(V(G),E(G)) is an undirected graph and σ:E(G)→{+,−} is a function which marks each edge with “+” or “−”. Two signed graphs are equivalent if one of them can be changed to the other by a sequence of resigning operations. The single resigning operation chooses a vertex v∈V(G) and flips the signs of all edges incident to v. By [G,σ] we shall denote the equivalence class of the signed graph (G,σ). Each element of [G,σ] is called a presentation of [G,σ]. In this paper we shall call both (G,σ) and [G,σ] signed graphs. The coloring of signed graphs is defined through homomorphism. The signed graph [G,σ] is colored by the signed graph (G2,σ2), if there exists a presentation (G,σ1) of [G,σ] and a vertex-mapping ϕ from G to G2 which preserves signs of the edges. In this paper we show that: (a) The signed chromatic number for the class G of all 2-dimensional grids lies between 5 and 6. (b) Every signed grid with at most seven rows can be colored with five colors. (c) Every signed grid with two rows can be colored with four colors.