Search the repository

A+ | A- | | SLO | ENG

Abstract: An open packing in a graph $G$ is a set $S$ of vertices in $G$ such that no two vertices in $S$ have a common neighbor in $G$. The injective chromatic number $\chi_i(G)$ of $G$ is the smallest number of colors assigned to vertices of ▫$G$▫ such that each color class is an open packing. Alternatively, the injective chromatic number of $G$ is the chromatic number of the two-step graph of $G$, which is the graph with the same vertex set as $G$ in which two vertices are adjacent if they have a common neighbor. The concept of injective coloring has been studied by many authors, while in the present paper we approach it from two novel perspectives, related to open packings and the two-step graph operation. We prove several general bounds on the injective chromatic number expressed in terms of the open packing number. In particular, we prove that $\chi_i(G) \ge \frac{1}{2}\sqrt{\frac{1}{4}+\frac{2m-n}{\rho^{o}}}$ holds for any connected graph $G$ of order $n\ge 2$, size $m$, and the open packing number ${\rho^{o}}$, and characterize the class of graphs attaining the bound. Regarding the well known bound $\chi_i(G)\ge \Delta(G)$, we describe the family of extremal graphs and prove that deciding when the equality holds (even for regular graphs) is NP-complete, solving an open problem from an earlier paper. Next, we consider the chromatic number of the two-step graph of a graph, and compare it with the clique number and the maximum degree of the graph. We present two large families of graphs in which $\chi_i(G)$ equals the cardinality of a largest clique of the two-step graph of $G$. Finally, we consider classes of graphs that admit an injective coloring in which all color classes are maximal open packings. We give characterizations of three subclasses of these graphs among graphs with diameter 2, and find a partial characterization of hypercubes with this property.
Keywords: two-step graph of a graph, injective coloring, open packing, hypercubes
Published in DiRROS: 09.04.2024; Views: 66; Downloads: 51
Full text (460,72 KB)
This document has many files! More...

Abstract: Given a graph $G$, a set $X$ of vertices in $G$ satisfying that between every two vertices in $X$ (respectively, in $G$) there is a shortest path whose internal vertices are not in $X$ is a mutual-visibility (respectively, total mutual-visibility) set in $G$. The cardinality of a largest (total) mutual-visibility set in $G$ is known under the name (total) mutual-visibility number, and has been studied in several recent works. In this paper, we propose two lower variants of these concepts, defined as the smallest possible cardinality among all maximal (total) mutual-visibility sets in $G$, and denote them by $\mu^{-}(G)$ and $\mu_t^{-}(G)$, respectively. While the total mutual-visibility number is never larger than the mutual-visibility number in a graph $G$, we prove that both differences $\mu^{-}(G)-\mu_t^{-}(G)$ and $\mu_t^{-}(G)-\mu^{-}(G)$ can be arbitrarily large. We characterize graphs $G$ with some small values of $\mu^{-}(G)$ and $\mu_t^{-}(G)$, and prove a useful tool called the Neighborhood Lemma, which enables us to find upper bounds on the lower mutual-visibility number in several classes of graphs. We compare the lower mutual-visibility number with the lower general position number, and find a close relationship with the Bollobás-Wessel theorem when this number is considered in Cartesian products of complete graphs. Finally, we also prove the NP-completeness of the decision problem related to $\mu_t^{-}(G)$.
Keywords: mutual-visibility set, mutual-visibility number, total mutual-visibility set, computational complexity
Published in DiRROS: 19.02.2024; Views: 145; Downloads: 64
Full text (567,18 KB)
This document has many files! More...