Do graph homomorphisms preserve forests?

101 Views Asked by At

A graph homomorphisms $\phi:G\rightarrow H$ is an adjacency preserving map between graphs $G$ and $H$. In other words, if $u,v\in V(G)$ are adjacent in $G$, written $u\sim v$, then we must have $\phi(u)\sim \phi(v)$ in $H$.

Any graph $G$ is a matroid $M=(E,\mathcal{I})$, where the ground set $E$ is the set of edges $E(G)$ and the independent sets $I\in\mathcal{I}$ are the forests (disjoint collections of trees) $F\subset E(G)$. To give more intuition, the dependent sets in a graph (as a matroid) are its cycles.

A (possible) definition of a matroid homomorphism is a map $\varphi: M \rightarrow N$, between matroids $M$ and $N$ which preserves independence, in the sense that if $I$ is independent in $M$, then $\varphi(I)$ must be independent in $N$.

Note: in graph theory the term independent set is often used synonymously with the term coclique (or stable sets). In this context, I mean an independent set in the matroid sense i.e. a forest when referring to a graph.

Question: Let $\phi:G\rightarrow H$ be an adjacency preserving map between graphs, is the image of each forest, $F$ in $G$, a forest $\phi(F)$ in $H$?

I think that one should consider non-simple graphs since loops are quite relevant in matroids.

Follow up question: Is there a study of forest preserving mappings between graphs? Or does this all get subsumed by graph minors?

1

There are 1 best solutions below

2
On BEST ANSWER

Not necessarily. Let $G$ be a graph on $\{0,1,2,\ldots, 19\}$ where there is an edge between $i$ and $j$ iff $|i-j|=1$ [no wraparound]. So 19 is adjacent to precisely 18, and 0 to precisely 1, and every other vertex has degree 2. This is a forest, a tree to be precise, actually a path on 20 vertices.

Then consider the mapping $\phi: G \mapsto \{0,1,2,3\}$ where $\phi(i) = i \mod 4$. Then $\phi(G)$ is a 4-cycle.