The channel assignment problem is the problem of assigning radio frequencies to transmitters while avoiding interference. This problem can be modeled and examined using graphs and graph colorings. \( L(2,1) \) coloring was first studied by Griggs and Yeh [6] as a model of a variation of the channel assignment problem. A no-hole coloring, introduced in [4], is defined to be an \( L(2,1) \) coloring of a graph which uses all the colors \(\{0,1,\ldots,k\}\) for some integer \(k\). An \( L(2,1) \) coloring is irreducible, introduced in [3], if no vertex labels in the graph can be decreased and yield another \( L(2,1) \) coloring. A graph \(G\) is inh-colorable if there exists an irreducible no-hole coloring on \(G\).

We consider the inh-colorability of bipartite graphs and Cartesian products. We obtain some sufficient conditions for bipartite graphs to be inh-colorable. We also find the optimal inh-coloring for some Cartesian products, including grid graphs and the rook’s graph.

Let \( G \) be a nontrivial connected graph of order \( n \) and \( k \) an integer with \( 2 \leq k \leq n \). For a set \( S \) of \( k \) vertices of \( G \), let \( \kappa(S) \) denote the maximum number \( \ell \) of pairwise edge-disjoint trees \( T_1, T_2, \ldots, T_\ell \) in \( G \) such that \( V(T_i) \cap V(T_j) = S \) for every pair \( i, j \) of distinct integers with \( 1 \leq i, j \leq \ell \). A collection \( \{T_1, T_2, \ldots, T_\ell\} \) of trees in \( G \) with this property is called a set of internally disjoint trees connecting \( S \). The \( k \)-connectivity \( \kappa_k(G) \) of \( G \) is defined as \( \kappa_k(G) = \text{min}\{\kappa(S)\} \), where the minimum is taken over all \( k \)-element subsets \( S \) of \( V(G) \). Thus \( \kappa_2(G) \) is the connectivity \( \kappa(G) \) of \( G \). In an edge-colored graph \( G \) in which adjacent edges may be colored the same, a tree \( T \) is a rainbow tree in \( G \) if no two edges of \( T \) are colored the same. For each integer \( \ell \) with \( 1 \leq \ell \leq \kappa_k(G) \), a \( (k, \ell) \)-rainbow coloring of \( G \) is an edge coloring of \( G \) (in which adjacent

Given a right-angled triangle of squares in a grid whose horizontal and vertical sides are \( n \) squares long, let \( N(n) \) denote the maximum number of dots that can be placed into the cells of the triangle such that each row, each column, and each diagonal parallel to the long side of the triangle contains at most one dot. It has been proven that \( N_f(n) = \lfloor \frac{2n+1}{3} \rfloor \). In this note, we give a new proof of the upper bound \( N_f(n) \leq \lfloor \frac{2n+1}{3} \rfloor \) using linear programming techniques.

In 1975, Leech introduced the problem of labeling the edges of a tree with distinct positive integers so that the sums along distinct paths in the tree were distinct, and the set of such path-sums were consecutive starting with one. We generalize this problem to labelings from arbitrary finite Abelian groups, with a particular focus on direct products of the additive group of \( \mathbb{Z}_2 \).

Let \( G \) be a simple graph. Any vertex labeling \( f: V(G) \to \mathbb{Z}_2 \) induces an edge labeling \( f^*: E(G) \to \mathbb{Z}_2 \) according to \( f^*(xy) = f(x) + f(y) \). For each \( i \in \mathbb{Z}_2 \), define \( v_f(i) = |\{v \in V(G) : f(v) = i\}| \), and \( e_f(i) = |\{e \in E(G) : f^*(e) = i\}| \). The friendly index set of the graph \( G \) is defined as \( \{|e_f(0) – e_f(1)| : |v_f(0) – v_f(1)| \leq 1\} \). We determine the friendly index sets of connected \( (p, p+1) \)-graphs with minimum degree \( 2 \). Many of them form arithmetic progressions. Those that are not miss only the second terms of the progressions.

We consider a storage/scheduling problem which, in addition to the standard restriction involving pairs of elements that cannot be placed together, considers pairs of elements that must be placed together. A set \( S \) is a colored-independent set if, for each color class \( V_i \), \( S \cap V_i = V_i \) or \( S \cap V_i = \emptyset \). In particular, \( \beta_{\mathrm{PRT}}(G) \), the independence-partition number, is determined for all paths of order \( n \). Finally, we show that the resulting decision problem for graphs is NP-complete even when the input graph is a path.

Given a partition \(\{P_1, \ldots, P_m\}\) of a \(v\)-set, a restricted simple \(1\)-design is a collection of distinct subsets (blocks) such that every element occurs in the same number of blocks, but any two elements from the same part do not occur together in the same block. We give a construction of restricted simple \(1\)-designs to show that the necessary conditions are sufficient for the existence of restricted simple \(1\)-designs.

An \((r, \lambda)\) overlap coloring of a graph \( G \) allocates \( r \) colors to each vertex subject to the condition that any pair of adjacent vertices shares exactly \( \lambda \) colors. The \((r, \lambda)\) overlap chromatic number of \( G \) is the least number of colors required for such a coloring. The overlap chromatic numbers of bipartite graphs are easy to find; those of odd cycle graphs have already been established. In this paper, we find the overlap chromatic numbers of the wheel graphs.

A family \(\mathcal{G}\) of connected graphs is a family with constant metric dimension if \(\dim(\mathcal{G})\) is finite and does not depend upon the choice of \(G\) in \(\mathcal{G}\).

The metric dimension of some classes of convex polytopes has been determined in \([8-12]\) and an open problem was raised in \([10]\): \emph{Let \(G\) be the graph of a convex polytope which is obtained by joining the graph of two different convex polytopes \(G_1\) and \(G_2\) (such that the outer cycle of \(G_1\) is the inner cycle of \(G_2\)) both having constant metric dimension. Is it the case that \(G\) will always have the constant metric dimension?}

In this paper, we study the metric dimension of an infinite class of convex polytopes which are obtained by the combinations of two different graphs of convex polytopes. It is shown that this infinite class of convex polytopes has constant metric dimension and only three vertices chosen appropriately suffice to resolve all the vertices of these classes of convex polytopes.

One natural extension of classical Ramsey numbers to multipartite graphs is to consider 2-colorings of the complete multipartite graph consisting of \( n \) parts, each of size \( k \), denoted \( K_{n \times k} \). We may then ask for the minimum integer \( n \) such that \( K_{n \times k} \rightarrow (G, H) \) for two given graphs \( G \) and \( H \). We study this number for the cases when \( G \) and \( H \) are paths or cycles and show some general bounds and relations to classical Ramsey theory.