The frequency assignment problem asks for assigning frequencies to transmitters in a wireless network and includes a variety of specific subproblems. In particular, the packing coloring problem comes from the regulations concerning the assignment of broadcast frequencies to radio stations. The problem is placed on a graph-theoretical footing and modeled as the packing chromatic number $\chi_{\rho}(G)$ of a graph $G$. The packing chromatic number of $G$ is the smallest integer $k$ such that the vertex set $V(G)$ can be partitioned into disjoint classes $X_1, . . . , X_k$, with the condition that vertices in $X_i$ have pairwise distance greater than $i$. The determination of the packing chromatic number is known to be \textbf{NP}-hard. This paper presents an integer linear programming model and a satisfiability test model for the packing coloring problem. The proposed models were applied for studying the packing chromatic numbers of Cartesian products of paths and cycles and for the packing chromatic numbers of some distance graphs.
COBISS.SI-ID: 21043464
The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $\Pi_1,\ldots,\Pi_k$, where $\Pi_i$, $i \in [k]$, is an $i$-packing. The following conjecture is posed and studied: if $G$ is a subcubic graph, then $\chi_{\rho}(S(G))\le 5$, where $S(G)$ is the subdivision of $G$. The conjecture is proved for all generalized prisms of cycles. To get this result it is proved that if $G$ is a generalized prism of a cycle, then $G$ is $(1,1,2,2)$-colorable if and only if $G$ is not the Petersen graph. The validity of the conjecture is further proved for graphs that can be obtained from generalized prisms in such a way that one of the two $n$-cycles in the edge set of a generalized prism is replaced by a union of cycles among which at most one is a 5-cycle. The packing chromatic number of graphs obtained by subdividing each of its edges a fixed number of times is also considered.
COBISS.SI-ID: 17889113
We answer positively the question of M. O. Albertson [M.O. Albertson, You can't paint yourself into a corner, J. Combin. Theory Ser. B 73(2) (1998) 189-194] asking whether every planar graph can be 5-list-colored even if it contains precolored vertices, as long as they are sufficiently far apart from each other. In order to prove this claim, we also give bounds on the sizes of graphs critical with respect to 5-list coloring. In particular, if $G$ is a planar graph, $H$ is a connected subgraph of $G$ and $L$ is an assignment of lists of colors to the vertices of $G$ such that $| L(v) | \geq 5$ for every $v \in V(G) \setminus V(H)$ and $G$ is not $L$-colorable, then $G$ contains a subgraph with $O(| H |^2)$ vertices that is not $L$-colorable.
COBISS.SI-ID: 17882713
It is very well-known that there are precisely two minimal non-planar graphs: $K_5$ and $K_{3,3}$ (degree 2 vertices being irrelevant in this context). In the language of crossing numbers, these are the only 1-crossing-critical graphs: they each have crossing number at least one, and every proper subgraph has crossing number less than one. In 1987, Kochol exhibited an infinite family of 3-connected, simple 2-crossing-critical graphs. In this work, we: (i) determine all the 3-connected 2-crossing-critical graphs that contain a subdivision of the Möbius Ladder $V_{10}$; (ii) show how to obtain all the not 3-connected 2-crossing-critical graphs from the 3-connected ones; (iii) show that there are only finitely many 3-connected 2-crossing-critical graphs not containing a subdivision of $V_{10}$; and (iv) determine all the 3-connected 2-crossing-critical graphs that do not contain a subdivision of $V_{8}$.
COBISS.SI-ID: 17611353
This paper concerns finite, edge-transitive direct and strong products, as well as infinite weak Cartesian products. We prove that the direct product of two connected, non-bipartite graphs is edge-transitive if and only if both factors are edge-transitive and at least one is arc-transitive, or one factor is edge-transitive and the other is a complete graph with loops at each vertex. Also, a strong product is edge-transitive if and only if all factors are complete graphs. In addition, a connected, infinite non-trivial Cartesian product graph $G$ is edge-transitive if and only if it is vertex-transitive and if $G$ is a finite weak Cartesian power of a connected, edge- and vertex-transitive graph $H$, or if $G$ is the weak Cartesian power of a connected, bipartite, edge-transitive graph $H$ that is not vertex-transitive.
COBISS.SI-ID: 17670745