We study a two-player game played on undirected graphs called Trail Trap , which is a variant of a game known as Partizan Edge Geography . One player starts by choosing any edge and moving a token from one endpoint to the other; the other player then chooses a different edge and does the same. Alternating turns, each player moves their token along an unused edge from its current vertex to an adjacent vertex, until one player cannot move and loses. We present an algorithm to determine which player has a winning strategy when the graph is a tree and partially characterize the trees on which a given player wins. Additionally, we show that it is NP-hard to determine if Player 2 has a winning strategy on Trail Trap from the starting position, even for connected bipartite planar graphs with maximum degree 4. We determine which player has a winning strategy for certain subclasses of complete bipartite graphs and grid graphs, and we propose several open problems for further study.

A colored eulerian digraph is an eulerian digraph $G$ where a color is assigned to the tail of each edge and a color is assigned to the head of each edge. A compatible circuit is an eulerian circuit such that for every two consecutive edges $uv$ and $vw$ of the circuit, the color of the head of $uv$ is different from the color of the tail of $vw$. Let $S_3$ be the set of vertices of outdegree and indegree three that have exactly three colors on the incident edges where each color appears on exactly one incoming and exactly one outgoing edge. In this paper we consider graphs where all the vertices are in $S_3$. We show that in several special cases we can determine if a graph has a compatible circuit. Our characterization in these cases give rise to a polynomial-time algorithm that determines the existence of a compatible circuit and provides a compatible circuit if one exists.

Let $G$ be an Eulerian digraph with a fixed edge coloring (not necessarily a proper edge coloring). A compatible circuit of $G$ is an Eulerian circuit such that every two consecutive edges in the circuit have different colors. We characterize the existence of compatible circuits for directed graphs avoiding certain vertices of outdegree three. Our result is analogous to a result of Kotzig for compatible circuits in edge-colored Eulerian undirected graphs. From our characterization for digraphs we develop a polynomial time algorithm that determines the existence of a compatible circuit in an edge-colored Eulerian digraph and produces a compatible circuit if one exists. Our results use the fact that rainbow spanning trees have been characterized in edge-colored undirected multigraphs. We provide another graph-theoretical proof of this fact.

The distinguishing chromatic number $\chi_{_D}(G)$ of a graph G is the least integer k such that there is a proper k-coloring of G which is not preserved by any nontrivial automorphism of G. We study the distinguishing chromatic number of Cartesian products of graphs by focusing on how much it can exceed the trivial lower bound of the chromatic number $\chi(\cdot)$. Our main result is that for every graph G, there exists a constant $d_G$ such that for all $d\geq d_G$ the distinguishing chromatic number of $G^d$ is at most $\chi(G) +1$, where $G^d$ is the Cartesian product of d copies of G. We also prove that for $d\geq5$, the Cartesian product of d complete graphs has distinguishing chromatic number at most one more than the corresponding chromatic number, and we determine the distinguishing chromatic number of hypercubes exactly.

The first-fit chromatic number of a graph is the number of colors needed in the worst case of a greedy coloring. It is also called the Grundy number, which is defined to be the maximum number of classes in an ordered partition of the vertex set of a graph G into independent sets $V_1, V_2, \dots, V_k$ so that for each $1\le i

A bar visibility representation of a graph G is a collection of horizontal bars in the plane corresponding to the vertices of G such that two vertices are adjacent if and only if the corresponding bars can be joined by an unobstructed vertical line segment. In a bar k-visibility graph, two vertices are adjacent if and only if the corresponding bars can be joined by a vertical line segment that intersects at most k other bars. Bar k-visibility graphs were introduced by Dean et al. [J. Graph Algorithms Appl., 11 (2007), pp. 45–59]. In this paper, we present sharp upper bounds on the maximum number of edges in a bar k-visibility graph on n vertices and the largest order of a complete bar k-visibility graph. We also discuss regular bar k-visibility graphs and forbidden induced subgraphs of bar k-visibility graphs.