We disprove a conjecture proposed in [Gaspers et al., Discrete Applied Mathematics, 2010] and provide a new upper bound for the minimum number of brushes required to continually parallel clean a clique.

The strong chromatic index \( \chi’_s(G) \) of a graph \( G \) is the smallest integer \( k \) such that \( G \) has a proper edge \( k \)-coloring with the condition that any two edges at distance at most 2 receive distinct colors. It is known that \( \chi’_s(G) \leq 3\Delta – 2 \) for any \( K_4 \)-minor free graph \( G \) with \( \Delta \geq 3 \). We give a polynomial algorithm in order \( O(|E(G)|(n\Delta^2 + 2n + 14\Delta)) \) to strong color the edges of a \( K_4 \)-minor free graph with \( 3\Delta – 2 \) colors where \( \Delta \geq 3 \).

We introduce a new representation of MOFS of type \( F(m\lambda; \lambda) \), as a linear combination of \( \{0,1\} \) arrays. We use this representation to give an elementary proof of the classical upper bound, together with a structural constraint on a set of MOFS achieving the upper bound. We then use this representation to establish a maximality criterion for a set of MOFS of type \( F(m\lambda; \lambda) \) when \( m \) is even and \( \lambda \) is odd, which simplifies and extends a previous analysis \cite{ref3} of the case when \( m = 2 \) and \( \lambda \) is odd.

Arboricity is a graph parameter akin to chromatic number, in that it seeks to partition the vertices into the smallest number of sparse subgraphs. Where for the chromatic number we are partitioning the vertices into independent sets, for the arboricity we want to partition the vertices into cycle-free subsets (i.e., forests). Arboricity is NP-hard in general, and our focus is on the arboricity of cographs. For arboricity two, we obtain the complete list of minimal cograph obstructions. These minimal obstructions do generalize to higher arboricities; however, we no longer have a complete list, and in fact, the number of minimal cograph obstructions grows exponentially with arboricity.

We obtain bounds on their size and the height of their cotrees. More generally, we consider the following common generalization of colouring and partition into forests: given non-negative integers \( p \) and \( q \), we ask if a given cograph \( G \) admits a vertex partition into \( p \) forests and \( q \) independent sets. We give a polynomial-time dynamic programming algorithm for this problem. In fact, the algorithm solves a more general problem which also includes several other problems such as finding a maximum \( q \)-colourable subgraph, maximum subgraph of arboricity-\( p \), minimum feedback vertex set and the minimum weight of a \( q \)-colourable feedback vertex set.

Motivated by problems involving triangle-decompositions of graphs, we examine the facet structure of the cone \( \tau_n \) of weighted graphs on \( n \) vertices generated by triangles. Our results include enumeration of facets for small \( n \), a construction producing facets of \( \tau_{n+1} \) from facets of \( \tau_n \), and an arithmetic condition on entries of the normal vectors. We also point out that a copy of \( \tau_n \) essentially appears via the perimeter inequalities at one vertex of the metric polytope.

We consider the problem of detecting an intruder in a network where there are two types of detecting devices available. One device can determine the distance from itself to the intruder and the other can see the vertex it occupies as well as all adjacent vertices. The problem is to determine how many devices are required and where they should be placed in order to determine a single intruder’s location. We show that on the one hand, finding the minimum number of devices required to do this is easy when the network is a tree with at most one leaf adjacent to any vertex, while on the other hand finding this number is an NP-complete problem even for trees with at most two leaves adjacent to any vertex.

We present a 2-edge-coloured analogue of the duality theorem for transitive tournaments and directed paths. Given a 2-edge-coloured path \( P \) whose edges alternate blue and red, we construct a 2-edge-coloured graph \( D \) so that for any 2-edge-coloured graph \( G \),

\[
P \to G \iff G \not\to D.
\]

The duals are simple to construct, in particular \(|V(D)| = |V(P)| -1.\)

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.

Let \( G \) be a graph with vertex set \( V \) and no isolated vertices. A subset \( S \subseteq V \) is a semipaired dominating set of \( G \) if every vertex in \( V \setminus S \) is adjacent to a vertex in \( S \) and \( S \) can be partitioned into two-element subsets such that the vertices in each subset are at most distance two apart. We present a method of building trees having a unique minimum semipaired dominating set.