A mapping of the set of undirected simple (loopless) graphs to itself is a linear operator if it maps the edgeless graph to the edgeless graph and maps the union of graphs to the union of their images. A linear operator preserves a set if it maps that set to itself. We study linear operators that map sets defined by the restriction of their chromatic number. For example the set of all graphs whose chromatic number is at least \(k\) for some fixed \(3\leq k\leq n\). We show these linear operators must be vertex permutations.
Vertex labeling, or coloring, of graphs has been an integral part of graph theory for a couple of centuries. The Four Color Theorem was conjectured by Francis Guthrie in 1852 (communicated by his advisor, Augustus De Morgan, to William Rowen Hamilton at that time) and was given a graph theoretic formulation in 1880 by Peter Guthrie Tait (See [3, Chapter 11] or https://en.wikipedia.org/wiki/Four_color_theorem). In this article we investigate the Boolean linear operators on the set of all undirected simple graphs that map sets defined be their chromatic number to themselves. These operators are usually determined to be vertex permutations.
Let \({{\mathcal G}_n}\) denote the set of simple (loopless) undirected graphs on the vertex set \(V=\{v_1, v_2, \dots v_n\}\). Throughout we let \(O\) denote the edgeless graph in \({\mathcal G}_n\) and \(K_t\) denote the complete graph on \(t\) vertices. A graph \(G\in{\mathcal G}_n\) is denoted \(G=(V,E)\) where \(V\) is the vertex set and \(E=E(G)\) is the set of edges. For \(G\) and \(H\) members of \({\mathcal G}_n\), we write \(G+H\), or \(G\cup H\), to denote the graph \((V,E(G)\cup E(H))\). A graph whose edge set is a singleton is called an edge graph. The union of two edge graphs is either a parallel pair of edges if the edges do not share a common vertex or a 2-star, or equivalently a 2-path, if the two edges share a vertex.
If \(S\) and \(T\) are sets, and \(S\) is a subset of \(T\) we write \(T\setminus S\) to denote the set of all members of \(T\) that are not members of \(S\). If \(H\) is a subgraph of \(G\) we write \(G\setminus H\) to be the graph whose edge set is the set of those edges of \(G\) that are not edges of \(H\). That is, if \(G\) and \(H\) are graphs and \(H=(V,E(H))\) is a subgraph of \(G=(V,E(G))\) we write \(G\setminus H\) to denote the graph \(G\setminus H= (V, E(G)\setminus E(H))\).
An \(s\)-coloring (or an \(s\)-labeling) of the vertex set, \(V\), is a mapping \(C:V\to\{c_1, c_2, \dots c_s\}\). The set of all vertices each labeled a specific label is called a color set. A coloring of the vertices of \(G\) is proper if the mapping, \(C\), is surjective and no edge of \(G\) has incident vertices in the same color set.
The chromatic number of \(G\), \(\chi(G)\), is the minimum number of labels needed to label the vertices of \(G\) such that no adjacent vertices are labeled with the same label. That is, the chromatic number of \(G\) is the minimum cardinality of the set of colors in any proper coloring of \(G\).
A graph \(G\in{\mathcal G}_n\) is said to be \(k\)-partite if the vertex set \(V\) can be partitioned into \(k\) disjoint nonempty subsets such that each edge of \(G\) has incident vertices in different subsets of the partition. \(G\) is said to be minimally \(k\)-partite if \(G\) is \(k\)-partite and not \((k-1)\)-partite.
A mapping \(T:{\mathcal G}_n\to{\mathcal G}_n\) is said to be a linear operator if \(T(O)=O\) and \(T(G\cup H) = T(G)\cup T(H)\). The mapping \(T\) is said to be singular if and only if \(T(x)=O\) for some \(x\neq O\). So \(T\) is nonsingular if and only if \(T(x)=O\) implies that \(x=O\). Note when considering mappings on \({\mathcal G}_n\), \(T\) being nonsingular does not imply \(T\) is invertible as in the vector space case over fields. If \(T\) maps every nonzero member of \({\mathcal G}_n\) to a fixed graph \(Y\in{\mathcal G}_n\) and maps \(O\) to \(O\) then it is a linear nonsingular operator on \({\mathcal G}_n\) but not invertible.
A linear operator on a set \({\mathcal X}\), \(L:{\mathcal X}\to {\mathcal X}\) is idempotent if \(L\circ L = L\). That is, for any \(x\in {\mathcal X}, L(L(x))=L(x)\).
A linear operator \(T\) on \({\mathcal G}_n\) is said to preserve a set \({\mathcal X}\subseteq {\mathcal G}_n\) if \(G\in {\mathcal X}\) implies that \(T(G)\in {\mathcal X}\).
In studying preserver problems on a set whose addition is Boolean, for example \({\mathcal G}_n\) with union as addition, we must use additional hypotheses since, for example, if \(T(G) =A\) for some \(A\in {\mathcal X}\subseteq{\mathcal G}_n\) for all \(G\in {\mathcal G}_n\), then \(T\) preserves \({\mathcal X}\). Thus we require that the operator be bijective, idempotent or that it preserve more than one set.
A linear operator \(T\) on \({\mathcal G}_n\) is said to strongly preserve a set \({\mathcal X}\subseteq {\mathcal G}_n\) if \(G\in {\mathcal X}\) if and only if \(T(G)\in {\mathcal X}\). That is, \(T\) strongly preserves \({\mathcal X}\) if \(T\) preserves \({\mathcal X}\) and \(T\) preserves \({\mathcal G}_n\setminus {\mathcal X}\).
Let \({\mathbb Z}\) denote the set of all integers and \({\mathbb Z}_+\) denote the set of positive integers. (\(0\notin{\mathbb Z}_+\))
Lemma 2.1. Let \(G\in{\mathcal G}_n\). Then \(\chi(G)=k\) if and only if \(G\) is minimally \(k\)-partite.
Proof. Suppose \(G\in{\mathcal G}_n\) is minimally \(k\)-partite. Let a \(k\)-partition of \(V\) be the sets \(V_1, V_2, \dots , V_k\). Label the vertices in \(V_q\) with the label \(q\), \(q=1,\dots , k\). Since the incident vertices of any edge in \(G\) must be in different subsets, the labeling is a \(k\) coloring. Thus \(\chi(G)\leq k\), since \(G\) is not \((k-1)\)-partite, There can be no \((k-1)\) labeling of the vertex set such that all edges have incident vertices with different labels. That is \(G\) is not \((k-1)\) colorable. That is \(\chi(G)=k\).
Now, Suppose \(\chi(G)=k\). Then let the labeling (coloring) of the vertices be \(C:V\to\{1, 2, \dots , k\}\). Let \(V_q=\{v\in V \mid C(v)=q\}\). Then \(V_1, V_2, \dots , V_k\) is a partition of \(V\) such that no edge of \(G\) has vertices in the same color set. That is, \(G\) is \(k\)-partite with vertex partition \(V_1, V_2, \dots , V_k\). Since \(\chi(G)=k\), there is no \((k-1)\) proper coloring of the vertices of \(G\) and hence can not be partitioned into \((k-1)\) sets without having some edge with incident vertices in the same color set. That is \(G\) is minimally \(k\)-partite. ◻
Lemma 2.2. Let \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator. Then the following are equivalent:
(a) \(T\) is injective;
(b) \(T\) is surjective;
(c) \(T\) is bijective.
Proof. This follows from the fact that \({\mathcal G}_n\) is finite. ◻
Lemma 2.3. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) is a bijective linear operator then \(T\) maps edge graphs to edge graphs and preserves the number of edges in a graph, i.e., \(|E(T(G))|=|E(G)|\) for any \(G\in{\mathcal G}_n\).
Proof. Since \(E(G)\) is finite, if \(T\) maps a graph of two or more edges to an edge graph, say \(T(H)=E\), an edge graph, and \(R\) and \(S\) are distinct edge graphs that are subgraphs of \(H\) then, since only \(O\) is mapped to \(O\), \(T(R)\cup T(S)\) is a subgraph of \(T(H)=E\). Thus, \(T(R)=E\) and \(T(S)=E\), since \(E\) has only \(O\) as a proper subgraph. This contradicts that \(T\) is bijective. Thus, only edge graphs can be mapped to edge graphs.
Now if \(|E(G)|=m\), there are \(m\) distinct edge graphs that are subgraphs of \(G\), say \(E_1,E_2,\dots, E_m\). Then the edge set of \(T(G)\) must be the set of edges whose edge graphs are the distinct edge graphs \(T(E_1), T(E_2),\dots, T(E_m)\) since \(G=\sum\limits_{q=1}^m E_q\) so that \(T(G)= \sum\limits_{q=1}^m T(E_q)\). That is the number of edges in \(T(G)\) is \(m\). That is \(T\) preserves the cardinality of the edge set of \(G\) or \(|E(T(G))|=|E(G)|\). ◻
Due to the relation between the chromatic number and the possibility of partitioning the vertex set to establish a partite graph we prove the following.
Lemma 2.4. Let \(G\in{\mathcal G}_n\). If \(0\leq q \leq k\leq n\) and \(\chi(G)=q\) then there is a graph \(R\) in \({\mathcal G}_n\) such that \(\chi(G\cup R)=k\).
Proof. Suppose that \(\chi(G)=q \leq k\). Since adding an edge to the graph \(G\) can only increase the chromatic by at most 1, the addition of at least \(k-q\) edges will result in a graph of chromatic number \(k\). This follows since adding all edges not in the edge set of \(G\) to \(G\) will create graphs of every chromatic number less than or equal to \(n\), since adding all the edges not in \(G\) to \(G\) results in the graph \(K_n\) whose chromatic number is \(n\). Let \(R\) be the graph in \({\mathcal G}_n\) whose edge set is the set of those edges added to \(G\) to yield a graph of chromatic number \(k\). Then \(\chi(G\cup R)=k\). ◻
Lemma 2.5. Let \(G\in{\mathcal G}_n\). If \(0\leq k \le q\leq n\) and \(\chi(G)=q\) then there is a subgraph \(H\) of \(G\) such that \(\chi(H)=k\). Further every subgraph of \(G\) has chromatic number at most \(q\).
Proof. Since \(\chi(O)=0\), adding the edges of \(G\) one at a time to \(O\) will yield a graph of each chromatic number less than or equal to \(\chi(G)\).
Further, no subgraph of a \(k\)-partite graph can be minimally \(q\)-partite for any \(q>k\). Thus no subgraph of \(G\) can have chromatic number greater than the chromatic number of \(G\). ◻
Next we have a basic theorem of semigroup theory which we prove for completeness.
Lemma 2.6. Let \({\mathcal{X}}\) be a finite set and \(\phi:{\mathcal{X}}\to{\mathcal{X}}\) be any mapping. Then there is some power of \(\phi\) that is idempotent.
Proof. Since \({\mathcal{X}}\) is finite, and \(\phi\) can be considered a subset of \({\mathcal{X}}\times{\mathcal{X}}\), the
set
\(\{\phi,\phi^2,\phi^3, \ldots,
\phi^\ell,\ldots \}\) must be finite. That is there are \(a,b\in{\mathbb Z}_+\), the set of
nonnegative integers, with \(1\leq a <
b\) such that \(\phi^a=\phi^b\).
Let \(d=b-a\), so that \(b=a+d\). Since \(\phi^a=\phi^b=\phi^{(a+d)}=\phi^a\circ\phi^d=\phi^b\circ\phi^d=\phi^{(a+d)}\circ\phi^d
=\phi^{(a+2d)}\). Continuing in this manner we find that for any
\(k\in{\mathbb Z}_+\), \(\phi^{(a+kd)}=\phi^a\).
Suppose that \(c\in{\mathbb Z}_+\) with \(c\geq a\). Then \(c=a+z\) for some \(z\in{\mathbb Z}_+\). Thus, \(\phi^{c+kd}=\phi^{(a+z+kd)}=\phi^{(a+kd)+z}=\phi^{(a+kd)}\circ\phi^z=\phi^a\circ\phi^z=\phi^{(a+z)}=\phi^c\). That is, for any \(c,k\in{\mathbb Z}_+\) with \(c\geq a\), \(\phi^{c+kd}=\phi^c\).
Now, \(b>a\) and \(d=b-a\) so \(d\geq 1\). Thus, \(ad\geq a\). It now follows, for \(c=ad\) above, that \(\phi^{(ad+kd)} = \phi^{ad}\). For \(k=a\) we have \((\phi^{ad})^2=\phi^{2ad}=\phi^{(ad+ad)}=\phi^{ad}\). That is, \(\phi^{ad}\) is idempotent. ◻
Let \({\mathcal U}_k=\{G\in{\mathcal G}_n|\chi(G)\geq k\}\), and let \({\mathcal Q}_k=\{G\in{\mathcal G}_n|\chi(G)=k\}\). In[1] the linear operators on \({\mathcal G}_n\) that preserve \({\mathcal Q}_k\) for all \(k\) were investigated, that is the preservers of \(\chi\), the chromatic number function. In this article we investigate the linear operators on \({\mathcal G}_n\) that preserve other sets defined by the chromatic number, for example \({\mathcal U}_k\) and \({\mathcal Q}_k\) for some fixed \(k\).
Lemma 3.1. Let \(L:{\mathcal G}_n\to{\mathcal G}_n\) be an idempotent linear operator that strongly preserves \({\mathcal U}_k\) for some \(k, 4\leq k\leq n\). Then \(L\) is the identity operator, and hence is bijective.
Proof. We first show that the image of an edge graph is itself. So, let \(L:{\mathcal G}_n\to{\mathcal G}_n\) be an idempotent linear operator that strongly preserves \({\mathcal U}_k\). Suppose that \(E\) is an edge graph whose image is not itself. Say, the edge graph \(F\neq E\) is a subgraph of \(L(E)\), so that \(L(F\cup L(E))=L(E)\). Then, \(L(F\cup E)=L(F)\cup L(E)=L(F)\cup L^2(E)=L(F)\cup L(L(E))=L(F\cup L(E))=L^2(E)=L(E).\) That is, \(L(E)=L(E\cup F)\).
Let \(H\) be a graph in \({\mathcal G}_n\) such that \(E\cup F\) is a subgraph of \(H\) and \(H\cong K_k\). This is possible since \(k\geq 4\). So, \(\chi(H)=k\) while \(\chi(H\setminus F)=k-1\) as seen by labeling the incident vertices of the edge in \(F\) with the same label. Then \(H\in {\mathcal U}_k\) while \(H\setminus F\notin{\mathcal U}_k\). But, since \(E\) is a subgraph of \(H\setminus F\), \(H\setminus F= (H\setminus F)\cup E\), and hence, \(L(H\setminus F)=L((H\setminus F) \cup E)=L(H\setminus F)\cup L(E)= L(H\setminus F)\cup L(E\cup F)=L((H\setminus F)\cup (E\cup F))=L(H)\), a contradiction to the assumption that \(L\) strongly preserves \({\mathcal U}_k\). That is, given any edge graph \(E\), \(L(E)=E\).
Let the set of all edge graphs in \({\mathcal G}_n\) be labeled so that \(E_q, q=1,2,\dots,m\) are the edge graphs of \({\mathcal G}_n\) where \(m={n\choose 2}\). Let \(G\in{\mathcal G}_n\). Then, for some index set \(I\subseteq \{1, 2, \dots, m\}\), \(G=\sum\limits_{q\in I} E_q\). Now, \(L(G)=L(\sum\limits_{q\in I} E_q)=\sum\limits_{q\in I} L(E_q)=\sum\limits_{q\in I} E_q=G\). So for any \(G\in{\mathcal G}_n\), \(L(G)=G\). ◻
Lemma 3.2. Let \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that strongly preserves \({\mathcal U}_k\) for some \(k, 4\leq k \leq n\). Then \(T\) is bijective.
Proof. Let \(T^p=L\) be idempotent, see Lemma 2.6. By Lemma 3.1 we know that \(L\) is bijective. But then, as \(L\) is a power of \(T\), \(T\) must also be bijective. ◻
Lemma 3.3. The number of graphs in \({\mathcal G}_n\) that are isomorphic to the complete graph on \(k\) vertices is \(n\choose k\). If \(P\) is a fixed 2-star, the number of graphs in \({\mathcal G}_n\) that are isomorphic to the complete graph on \(k\) vertices that contain the subgraph \(P\) is \({n-3}\choose {k-3}\). If \(Q\) is a fixed graph of two non adjacent edges, the number of graphs in \({\mathcal G}_n\) that are isomorphic to the complete graph on \(k\) vertices that contain the subgraph \(Q\) is \({n-4}\choose {k-4}\).
Proof. A graph in \({\mathcal G}_n\) that is isomorphic to the complete graph on \(k\) vertices is completely determined by the non isolated vertices. There are precisely \(n\choose k\) such distinct sets of vertices.
A graph in \({\mathcal G}_n\) that is isomorphic to the complete graph on \(k\) vertices that contain a fixed subgraph on \(t\) vertices is completely determined by the \(t\) vertices of the fixed subgraph together with the \(k-t\) other non isolated vertices. There are precisely \(n-t\choose k-t\) such distinct sets of vertices. A fixed 2-star fixes 3 vertices and a fixed pair of non adjacent edges fixes four vertices. ◻
The next theorem uses the following lemma from[2]:
Lemma 3.4. [2, Lemma 2.2] If \(T:{\mathcal G}_n\to{\mathcal G}_n\) is bijective, preserves \(|E(G)|\) the size of the graph, and maps 2-stars to 2-stars then \(T\) is a vertex permutation.
Theorem 3.5. Let \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that strongly preserves \({\mathcal U}_k\) for some \(k, 4\leq k \leq n\). Then \(T\) is a vertex permutation.
Proof. Since \(T\) is bijective by Lemma 3.2 and \(T\) preserves \(|E(G)|\) the size of the graph by Lemma 2.3, then by Lemma 3.4 we only need show that \(T\) maps 2-stars to 2-stars.
Suppose that \(E\) and \(F\) are adjacent edge graphs so that \(E\cup F\) is a 2-star and \(T(E\cup F)\) is not a 2-star. Since \(T\) preserves \(|E(G)|\), \(T(E\cup F)\) must be a pair of non adjacent edges. Since \(T\) preserves \(|E(G)|\) and strongly preserves \({\mathcal U}_k\), it maps graphs of minimum size in \({\mathcal U}_k\) to graphs of minimum size in \({\mathcal U}_k\). The graphs of minimum size in \({\mathcal U}_k\) are all isomorphic to \(K_k\). Thus, if \(T\) maps a 2-star to a pair of nonadjacent edges, the number of graphs in \({\mathcal G}_n\) that are isomorphic to the complete graph on \(k\) vertices that contain the fixed 2-star must be the same as the number of graphs in \({\mathcal G}_n\) that are isomorphic to the complete graph on \(k\) vertices that contain the fixed graph of two non adjacent edges. Thus, \({{n-3}\choose {k-3}} ={{n-4}\choose {k-4}}\), an impossibility since \(n>k\). Thus \(T\) maps 2-stars to 2-stars, and hence by Lemma 3.4, \(T\) is a vertex permutation. ◻
Theorem 4.1.Let \(4\leq k \leq n\) and \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that strongly preserves \({\mathcal Q}_k\). Then \(T\) strongly preserves \({\mathcal U}_k\).
Proof. Suppose that \(4\leq k < n\). We show that \(T\) preserves \({\mathcal G}_n\setminus{\mathcal U}_k\) and then that \(T\) preserves \({\mathcal U}_k\). Suppose that \(G\in{\mathcal G}_n\setminus {\mathcal U}_k\), so \(\chi(G)<k\), and further that \(\chi(T(G))\geq k\). Then \(\chi(T(G))>k\) since \(T\) strongly preserves \({\mathcal Q}_k\). Since \(\chi(G)<k\), by Lemma 2.4 there is some graph \(R\) in \({\mathcal G}_n\) such that \(\chi(G\cup R)=k\). But then, \(k = \chi(G\cup R)=\chi(T(G\cup R)) = \chi(T(G)\cup T(R)) \geq \chi(T(G)) > k\), a contradiction. Thus \(G\in {\mathcal G}_n\setminus {\mathcal U}_k\). That is, \(T\) preserves \({\mathcal G}_n\setminus{\mathcal U}_k\).
Now, suppose \(G\in{\mathcal U}_k\). Then \(\chi(G)\geq k\). Now, for some subgraph of \(G\) \(R\leq G\), by Lemma 2.5 \(\chi(R)=k\). and hence \(\chi(T(R))=k\). So, \(\chi(T(G))\geq \chi(T(R))=k\). That is \(T(G)\in{\mathcal U}_k\). Thus \(T\) preserves \({\mathcal U}_k\). We now have that \(T\) strongly preserves \({\mathcal U}_k\) if \(k<n\).
Now, suppose that \(k=n\). Then, since there are no graphs in \({\mathcal G}_n\) of chromatic number larger than \(n\), \({\mathcal Q}_n={\mathcal U}_n\). Thus \(T\) strongly preserves \({\mathcal Q}_n\) if and only if \(T\) strongly preserves \({\mathcal U}_n\). ◻
Theorem 4.2. Let \(4\leq k \leq n\) and \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that preserves \({\mathcal Q}_k\) and preserves \({\mathcal Q}_{k-1}\). Then \(T\) strongly preserves \({\mathcal U}_k\).
Proof. We show that \(T\) preserves \({\mathcal G}_n\setminus {\mathcal U}_k\) and then that \(T\) preserves \({\mathcal U}_k\). Suppose that \(G\in{\mathcal G}_n\setminus {\mathcal U}_k\), so \(\chi(G)\leq k-1\). Then, by Lemma 2.4, there is a graph \(R\in{\mathcal G}_n\) such that \(\chi(G\cup R) = k-1\). Since \(G\leq G\cup R\), \(\chi(T(G))\leq\chi(T(G\cup R)) = k-1\), Hence, \(T(G)\in {\mathcal G}_n\setminus {\mathcal U}_k\). That is, \(T\) preserves \({\mathcal G}_n\setminus {\mathcal U}_k\).
Now, suppose \(G\in{\mathcal U}_k\). Then \(\chi(G)\geq k\). Now, by Lemma 2.5, for some subgraph \(R\) of \(G\), \(\chi(R)=k\). and hence \(\chi(T(R))=k\). So, \(\chi(T(G))\geq \chi(T(R))=k\). That is, \(T(G)\in{\mathcal U}_k\). Thus, \(T\) preserves \({\mathcal U}_k\). It now follows that \(T\) strongly preserves \({\mathcal U}_k\). ◻
The proofs in this section are similar to the ones in Sections 3 and 4, and are included here for completeness.
Lemma 5.1. Let \(T:{\mathcal G}_n\to{\mathcal G}_n\) be an idempotent linear operator that strongly preserves \({\mathcal U}_3\). Then \(T\) is the identity operator, and hence is bijective.
Proof.We first show that the image of an edge graph is itself. So, let \(L:{\mathcal G}_n\to{\mathcal G}_n\) be an idempotent linear operator that strongly preserves \({\mathcal U}_3\). Suppose that \(E\) is an edge graph whose image is not itself. Say, the edge graph \(F\neq E\) is a subgraph of \(L(E)\). Then, \(L(F\cup E)=L(F)\cup L(E)=L(F)\cup L^2(E)=L(F)\cup L(L(E))=L(F\cup L(E))=L^2(E)=L(E).\) That is, \(L(E)=L(E\cup F)\).
Case 1. \(E\) and \(F\) are adjacent. In this case, \(E\cup F\) is a subgraph of some graph isomorphic to \(K_3\), a triangle. Let \(H\) be a graph in \({\mathcal G}_n\) such that \(E\cup F\) is a subgraph of \(H\) and \(H\cong K_3\). So, \(\chi(H)=3\) while \(\chi(H\setminus F)=2\). Then \(H\in {\mathcal U}_3\) while \(H\setminus F\notin{\mathcal U}_3\). But, since \(E\) is a subgraph of \(H\setminus F\), \(H\setminus F= (H\setminus F)\cup E\), and hence, \(L(H\setminus F)=L((H\setminus F) \cup E)=L(H\setminus F)\cup L(E)= L(H\setminus F)\cup L(E\cup F)=L((H\setminus F)\cup (E\cup F))=L(H)\), a contradiction to the assumption that \(L\) strongly preserves \({\mathcal U}_3\). That is, given any edge graph \(E\), \(L(E)=E\).
Case 2. \(E\) and \(F\) are nonadjacent. Let \(K_3^+\) be the graph of four edges consisting of a triangle plus one attached edge, a \(K_3\) with one pendent edge. Then, \(E\cup F\) is a subgraph of some graph \(Q\) which is isomorphic to \(K_3^+\). Here, either \(Q\setminus E\) or \(Q\setminus F\) has chromatic number 2, say \(Q\setminus F\). (It is a 3-star, 3 edges sharing a common vertex.) So, \(\chi(Q)=3\) while \(\chi(Q\setminus F)=2\). Then \(Q\in {\mathcal U}_3\) while \(Q\setminus F\notin{\mathcal U}_3\). But, since \(E\) is a subgraph of \(Q\setminus F\), \(Q\setminus F= (Q\setminus F)\cup E\), and hence, \(L(Q\setminus F)=L((Q\setminus F) \cup E)=L(Q\setminus F)\cup L(E)= L(Q\setminus F)\cup L(E\cup F)=L((Q\setminus F)\cup (E\cup F))=L(Q)\), a contradiction to the assumption that \(L\) strongly preserves \({\mathcal U}_3\). That is, given any edge graph \(E\), \(L(E)=E\).
Now, in either case we have \(L(E)=E\) for any edge graph \(E\). Let the set of all edge graphs in \({\mathcal G}_n\) be labeled so that \(E_q, q=1,2,\dots,m\) are the edge graphs of \({\mathcal G}_n\) where \(m={n\choose 2}\). Let \(G\in{\mathcal G}_n\). Then, for some index set \(I\subseteq \{1, 2, \dots, m\}\), \(G=\sum\limits_{q\in I} E_q\). Now, \(L(G)=L(\sum\limits_{q\in I} E_q)=\sum\limits_{q\in I} L(E_q)=\sum\limits_{q\in I} E_q=G\). So for any \(G\in{\mathcal G}_n\), \(L(G)=G\). ◻
Lemma 5.2. Let \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that strongly preserves \({\mathcal U}_3\). Then \(T\) is bijective.
Proof. Let \(T^p=L\) be idempotent, see Lemma 2.6. By Lemma 5.1 we know that \(L\) is bijective. But then, as \(L\) is a power of \(T\), \(T\) must also be bijective. ◻
Theorem 5.3. Let \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that strongly preserves \({\mathcal U}_3\). Then \(T\) is a vertex permutation.
Proof. Since \(T\) is bijective by Lemma 5.2 and \(T\) preserves \(|E(G)|\) the size of the graph by Lemma 2.3, then by Lemma 3.4 we only need show that \(T\) maps 2-stars to 2-stars.
Since any pair of edges in a triangle form a 2-star and the image of any triangle graph must be a triangle graph, \(T\) preserves 2-stars. By Lemma 3.4, \(T\) is a vertex permutation. ◻
Theorem 5.4. Let \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that strongly preserves \({\mathcal Q}_3\). Then \(T\) is a vertex permutation.
Proof. We show that \(T\) preserves \({\mathcal G}_n\setminus {\mathcal U}_3\) and then that \(T\) preserves \({\mathcal U}_3\). Suppose that \(O\neq G\in{\mathcal G}_n\setminus {\mathcal U}_3\), so \(\chi(G)=2\), and suppose further that \(\chi(T(G))\geq 3\). If \(n=3\) we arrive at a contradiction since \(T\) strongly preserves \({\mathcal Q}_3\). Now, assume \(n>3\). Then \(\chi(T(G))>3\) since \(T\) strongly preserves \({\mathcal Q}_3\). Since \(\chi(G)=2\), there is some graph \(R\) in \({\mathcal G}_n\) such that \(\chi(G\cup R)=3\). But then, \(3 = \chi(G\cup R)=\chi(T(G\cup R)) = \chi(T(G)\cup T(R)) \geq \chi(T(G)) > 3\), a contradiction. Thus \(G\in {\mathcal G}_n\setminus {\mathcal U}_k\). That is, \(T\) preserves \({\mathcal G}_n\setminus{\mathcal U}_3\).
Now, suppose \(G\in{\mathcal U}_3\). Then \(\chi(G)\geq 3\). Now, for some subgraph of \(G\) \(R\leq G\), \(\chi(R)=3\). and hence \(\chi(T(R))=3\). So, \(\chi(T(G))\geq \chi(T(R))=3\). That is, \(T(G)\in{\mathcal U}_3\). Thus, \(T\) preserves \({\mathcal U}_3\). It now follows that \(T\) strongly preserves \({\mathcal U}_3\).
By Theorem 5.3, \(T\) is a vertex permutation. ◻
Theorem 5.5. Let \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that preserves \({\mathcal Q}_{3}\) and preserves \({\mathcal Q}_{2}\). Then \(T\) strongly preserves \({\mathcal U}_3\).
Proof. The proof is parallel to the above proof of Theorem 5.4 or the proof of Theorem 4.2. ◻
The set \({\mathcal U}_2\) is precisely \({\mathcal G}_n\setminus O\), so any nonsingular linear operator strongly preserves \({\mathcal U}_2\).
If \(T:{\mathcal G}_n\to{\mathcal G}_n\) is a linear operator that strongly preserves \({\mathcal Q}_2\), then \(T\) strongly preserves \({\mathcal U}_3\) since the only graphs not in \({\mathcal U}_3\) are precisely the graphs in \({\mathcal Q}_2\) together with \(O\). Thus \(T:{\mathcal G}_n\to{\mathcal G}_n\) is a linear operator that strongly preserves \({\mathcal Q}_2\) if and only if, by Theorem 5.3, \(T\) is a vertex permutation.
Corollary 6.1. Let \(3\leq k \leq n\) and \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator, then the following are equivalent:
1. \(T\) strongly preserves \({\mathcal U}_k\), the graphs in \({\mathcal G}_n\) of chromatic number at least \(k\);
2. \(T\) strongly preserves \({\mathcal Q}_k\), the set of graphs in \({\mathcal G}_n\) of chromatic number \(k\);
3. \(T\) preserves \({\mathcal Q}_k\) and \({\mathcal Q}_{k-1}\);
\(T\) is a vertex permutation.
Proof. Let \(k>3\). By Theorem 3.5, statement 1) implies statement 4). By Theorem 4.1 statement 2) implies statement 1). By Theorem 4.2, statement 3) implies statement 1). Clearly, any vertex permutation preserves (strongly) any of the sets \({\mathcal U}_k\) and \({\mathcal Q}_k\) for all \(k\). Therefore statement 4) implies statements 1), 2), and 3).
Now, let \(k=3\). By Theorem 5.3, statement 1) implies statement 4). By Theorem 5.4 statement 2) implies statement 4). By Theorem 5.5, statement 3) implies statement 1). Clearly, any vertex permutation preserves (strongly) both of the sets \({\mathcal U}_{3}\) and \({\mathcal Q}_{3}\). Therefore statement 4) implies statements 1), 2), and 3). ◻