Let G1 and G2 be copies of a graph G, and let f : V (G1) → V (G2) be a function. Then a functigraph C(G, f) = (V, E) is a generalization of a permutation graph, where V = V (G1) ∪ V (G2) and E = E(G1) ∪ E(G2) ∪ {uv : u ∈ V (G1), v ∈ V (G2), v = f(u)}. In this paper, we study colorability and planarity of functigraphs.
A graph is 2-stratified if its vertex set is partitioned into two classes, where the vertices in one class are colored red and those in the other class are colored blue. Let F be a 2-stratified graph rooted at some blue vertex v. An F-coloring of a graph G is a red-blue coloring of the vertices of G in which every blue vertex v belongs to a copy of F rooted at v. The F-domination number γF (G) is the minimum number of red vertices in an F-coloring of G. In this paper, we study F-domination where F is a red-blue-blue path of order 3 rooted at a blue end-vertex. It is shown that a triple (A, B, C) of positive integers with A ≤ B ≤ 2A and B ≥ 2 is realizable as the domination number, open domination number, and F-domination number, respectively, for some connected graph if and only if (A, B, C) ≠ (k, k, C) for any integers k and C with C > k ≥ 2.
For a nontrivial connected graph G, let c : V (G) → N be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v ∈ V (G), the neighborhood color set NC(v) is the set of colors of the neighbors of v. The coloring c is called a set coloring if NC(u) 6= NC(v) for every pair u, v of adjacent vertices of G. The minimum number of colors required of such a coloring is called the set chromatic number χs(G). We show that the decision variant of determining χs(G) is NP-complete in the general case, and show that χs(G) can be efficiently calculated when G is a threshold graph. We study the difference χ(G) − χs(G), presenting new bounds that are sharp for all graphs G satisfying χ(G) = ω(G). We finally present results of the Nordhaus-Gaddum type, giving sharp bounds on the sum and product of χs(G) and χs(G).