An edge coloring \( c \) of a graph \( G \) is a royal \( k \)-edge coloring of \( G \) if the edges of \( G \) are assigned nonempty subsets of the set \( \{1,2,\dots,k\} \) in such a way that the vertex coloring obtained by assigning the union of the colors of the incident edges of each vertex is a proper vertex coloring. If the vertex coloring is vertex-distinguishing, then \( c \) is a strong royal \( k \)-edge coloring. The minimum positive integer \( k \) for which \( G \) has a strong royal \( k \)-edge coloring is the strong royal index of \( G \). It has been conjectured that if \( G \) is a connected graph of order \( n \geq 4 \) where \( 2^{k-1} \leq n \leq 2^k – 1 \) for a positive integer \( k \), then the strong royal index of \( G \) is either \( k \) or \( k+1 \). We discuss this conjecture along with other information concerning strong royal colorings of graphs. A sufficient condition for such a graph to have strong royal index \( k+1 \) is presented.

Let \( k \) be a positive integer, and \( G \) be a \( k \)-connected graph. An edge-coloured path is rainbow if all of its edges have distinct colours. The rainbow \( k \)-connection number of \( G \), denoted by \( rc_k(G) \), is the minimum number of colours in an edge-colouring of \( G \) such that, any two vertices are connected by \( k \) internally vertex-disjoint rainbow paths. The function \( rc_k(G) \) was introduced by Chartrand, Johns, McKeon, and Zhang in 2009, and has since attracted significant interest. Let \( t_k(n,r) \) denote the minimum number of edges in a \( k \)-connected graph \( G \) on \( n \) vertices with \( rc_k(G) \leq r \). Let \( s_k(n,r) \) denote the maximum number of edges in a \( k \)-connected graph \( G \) on \( n \) vertices with \( rc_k(G) \geq r \). The functions \( t_1(n,r) \) and \( s_1(n,r) \) have previously been studied by various authors. In this paper, we study the functions \( t_2(n,r) \) and \( s_2(n,r) \). We determine bounds for \( t_2(n,r) \) which imply that \( t_2(n,2) = (1 + o(1)) n \log_2 n \), and \( t_2(n,r) \) is linear in \( n \) for \( r \geq 3 \). We also provide some remarks about the function \( s_2(n,r) \).

A signed graph \( (G, \sigma) \) is a graph \( G \) together with a mapping \( \sigma \) which assigns to each edge of \( G \) a sign, either positive or negative. The sign of a closed walk in \( (G, \sigma) \) is the product of the signs of its edges (considering multiplicity). Considering signs of closed walks as one of the key structures of signed graphs, a homomorphism of a signed graph \( (G, \sigma) \) to a signed graph \( (H, \pi) \) is defined to be a mapping that maps vertices to vertices, edges to edges, and that preserves incidences, adjacencies, and signs of closed walks. This is a recently defined notion, closely related to sign-preserving homomorphisms of signed graphs (or, equivalently, to homomorphisms of 2-edge-colored graphs), that helps, in particular, to establish a stronger connection between the theories of coloring and homomorphisms of graphs and the minor theory of graphs.

When there exists a homomorphism of \( (G, \sigma) \) to \( (H, \pi) \), one may write \( (G, \sigma) \to (H, \pi) \), thus extending the graph homomorphism order to a partial order on the classes of homomorphically equivalent signed graphs. In this work, studying this order, we prove that this order forms a lattice. That is to say, for each pair \( (G_1, \sigma_1) \) and \( (G_2, \sigma_2) \) of signed graphs, representing their respective classes, both their join and meet exist. While proving this result, we also show the existence of categorical products for signed graphs.

The game of cops and robbers on a graph is a vertex pursuit game played by two players with perfect information. Per the rules of the game, a given graph is either inherently cop-win or robber-win. It is possible that adding any edge changes the inherent nature of a particular graph. Such a graph is maximal in the sense that no edge can be added without changing its “win-state”. Furthermore, if deleting any edge changes the “win-state”, then this graph is minimal. Join us as we walk this thin blue line between cop-win and robber-win and explore the good, the bad, and the ugly.

Let \( H \) be a hypergraph of order \( n_H = |V(H)| \) and size \( m_H = |E(H)| \). The transversal number \( \tau(H) \) of a hypergraph \( H \) is the minimum number of vertices that intersect every edge of \( H \). A linear hypergraph is one in which every two distinct edges intersect in at most one vertex. A \( k \)-uniform hypergraph has all edges of size \( k \). For \( k \geq 2 \), let \( \mathcal{L}_k \) denote the class of \( k \)-uniform linear hypergraphs. We consider the problem of determining the best possible constants \( q_k \) (which depends only on \( k \)) such that \( \tau(H) \leq q_k(n_H + m_H) \) for all \( H \in \mathcal{L}_k \). It is known that \( q_2 = \frac{1}{3} \) and \( q_3 = \frac{1}{4} \). In this paper we show that \( q_4 = \frac{1}{5} \), which is better than for non-linear hypergraphs. Using the affine plane \( AG(2,4) \) of order 4, we show there are a large number of densities of hypergraphs \( H \in \mathcal{L}_4 \) such that \( \tau(H) = \frac{1}{5} (n_H + m_H) \).

Let \( F \) be a (possibly improper) edge-coloring of a graph \( G \); a vertex coloring of \( G \) is adapted to \( F \) if no color appears at the same time on an edge and on its two endpoints. If for some integer \( k \), a graph \( G \) is such that given any list assignment \( L \) to the vertices of \( G \), with \( |L(v)| \geq k \) for all \( v \), and any edge-coloring \( F \) of \( G \), \( G \) admits a coloring \( c \) adapted to \( F \) where \( c(v) \in L(v) \) for all \( v \), then \( G \) is said to be adaptably k-choosable. A \((k,d)\)-list assignment for a graph \( G \) is a map that assigns to each vertex \( v \) a list \( L(v) \) of at least \( k \) colors such that \( |L(x) \cap L(y)| \leq d \) whenever \( x \) and \( y \) are adjacent. A graph is \((k,d)\)-choosable if for every \((k,d)\)-list assignment \( L \) there is an \( L \)-coloring of \( G \). It has been conjectured that planar graphs are \((3,1)\)-choosable. We give some progress on this conjecture by giving sufficient conditions for a planar graph to be adaptably 3-choosable. Since \((k,1)\)-choosability is a special case of adaptable \( k \)-choosability, this implies that a planar graph satisfying these conditions is \((3,1)\)-choosable.

A broadcast on a nontrivial connected graph \( G = (V,E) \) is a function \( f : V \to \{0,1,\dots,\operatorname{diam}(G)\} \) such that \( f(v) \leq e(v) \) (the eccentricity of \( v \)) for all \( v \in V \). The weight of \( f \) is \( \sigma(f) = \sum_{v \in V} f(v) \). A vertex \( u \) hears \( f \) from \( v \) if \( f(v) > 0 \) and \( d(u,v) \leq f(v) \). A broadcast \( f \) is independent, or hearing independent, if no vertex \( u \) with \( f(u) > 0 \) hears \( f \) from any other vertex \( v \). We define a different type of independent broadcast, namely a boundary independent broadcast, as a broadcast \( f \) such that, if a vertex \( w \) hears \( f \) from vertices \( v_1, \dots, v_k \), \( k \geq 2 \), then \( d(w,v_i) = f(v_i) \) for each \( i \). The maximum weights of a hearing independent broadcast and a boundary independent broadcast are the \textit{hearing independence broadcast number} \( \alpha_h(G) \) and the boundary independence broadcast number \( \alpha_{bn}(G) \), respectively.

We prove that \( \alpha_{bn}(G) = \alpha(G) \) (the independence number) for any 2-connected bipartite graph \( G \) and that \( \alpha_{bn}(G) \leq n – 1 \) for all graphs \( G \) of order \( n \), characterizing graphs for which equality holds. We compare \( \alpha_{bn} \) and \( \alpha_h \) and prove that although the difference \( \alpha_h – \alpha_{bn} \) can be arbitrary, the ratio is bounded, namely \( \alpha_h / \alpha_{bn} < 2 \), which is asymptotically best possible. We deduce that \( \alpha_h(G) \leq 2n – 5 \) for all connected graphs \( G \neq P_n \) of order \( n \), which improves an existing upper bound for \( \alpha_h(G) \) when \( \alpha(G) \geq n/2 \).

We continue our studies of burn-off chip-firing games from Discrete Math. Theor. Comput. Sci. 15 (2013), no. 1, 121–132; MR3040546] and Australas. J. Combin. 68 (2017), no. 3, 330–345; MR3656659]. The latter article introduced randomness by choosing successive seeds uniformly from the vertex set of a graph \( G \). The length of a game is the number of vertices that fire (by sending a chip to each neighbor and annihilating one chip) as an excited chip configuration passes to a relaxed state. This article determines the probability distribution of the game length in a long sequence of burn-off games. Our main results give exact counts for the number of pairs \( (C, v) \), with \( C \) a relaxed legal configuration and \( v \) a seed, corresponding to each possible length. In support, we give our own proof of the well-known equicardinality of the set \( R \) of relaxed legal configurations on \( G \) and the set of spanning trees in the cone \( G^* \) of \( G \). We present an algorithmic, bijective proof of this correspondence.

We study homomorphism properties of signed \( K_4 \)-minor-free graphs. On the one hand, we give a necessary and sufficient condition for a signed graph \( B \) to admit a homomorphism from any signed \( K_4 \)-minor-free graph and we determine the smallest of all such signed graphs. On the other hand, we characterize the minimal cores that do not belong to the class of signed \( K_4 \)-minor-free graphs. This, in particular, gives a classification of odd-\( K_4 \)’s that are cores. Furthermore, we show some applications of our work.

Game coloring is a two-player game in which each player properly colors one vertex of a graph at a time until all the vertices are colored. An “eternal” version of game coloring is introduced in this paper in which the vertices are colored and re-colored from over a sequence of rounds. In a given round, each vertex is colored, or re-colored, once, so that a proper coloring is maintained. Player 1 wants to maintain a proper coloring forever, while player 2 wants to force the coloring process to fail. The eternal game chromatic number of a graph \( G \) is defined to be the minimum number of colors needed in the color set so that player 1 can always win the game on \( G \). The goal of this paper is to introduce this problem, consider several variations of this game, show its behavior on some elementary classes of graphs, and make some conjectures.