From Connectivity to Coloring

Abstract

A vertex set $U\subset V$ in a connected graph $G=(V,E)$ is a cutset if $G–U$ is disconnected. If no proper subset of $U$ is also a cutset of $G$, then $U$ is a minimal cutset. An $\mathcal{M}\mathcal{V}\mathcal{C}$-partition $\pi =\{V_1,V_2,\dots ,V_k\}$ of the vertex set $V(G)$ of a connected graph $G$ is a partition of $V(G)$ such that every $V_i\in \pi$ is a minimal cutset of $G$. For an $\mathcal{M}\mathcal{V}\mathcal{C}$-partition $\pi$ of $G$, the $\pi$-graph $G_{\pi }$, of $G$ has vertex set $\pi$ such that $V^{\prime },V”\in \pi$ are adjacent in $G_{\pi }$, if and only if there exist $v^{\prime }\in V^{\prime }$ and $v”\in V”$ such that $v^{\prime }v”\in E(G)$. Graphs that are a $\pi$- graphs of cycles are characterized. A homomorphic image $H$ of a graph $G$ can be obtained from a partition $\mathcal{P}=V_1,V_2,\dots ,V_k$ of $V(G)$ into independent sets such that $V(H)=v_1,v_2,\dots ,v_k$, where $v_i$ is adjacent to $v_j$; if and only if some vertex of $V_j$ is adjacent to some vertex of $V_j$ in $G$. By investigating graphs $H$ that are homomorphic images of the Cartesian product $H\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{K}_2$, it is shown that for every nontrivial connected graph $H$ and every integer $r\ge 2$, there exists an $r$-regular graph $G$ such that $H$ is a homomorphic image of $G$. It is also shown that every nontrivial tree $T$ is a homomorphic image of $T\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{K}_2$ but that not all graphs $H$ are homomorphic images of $H\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{K}_2$.