From Connectivity to Coloring

Gary Chartrand1, Teresa W. Haynes2, Stephen T. Hedetniemi3, Ping Zhang4
1Department of Mathematics Western Michigan University Kalamazoo, MI 49008-5248, USA
2Department of Mathematics and Statistics East Tennessee State University Johnson City, TN 37614-0002 USA
3Department of Mathematics University of Johannesburg Auckland Park, 2006 South Africa
4 Department of Mathematics Western Michigan University Kalamazoo, MI 49008-5248, USA

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{MVC}\)-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{MVC}\)-partition \(\pi\) of \(G\), the \(\pi\)-graph \(G_{\pi}\), of \(G\) has vertex set \(\pi\) such that \(V’,V” \in \pi\) are adjacent in \(G_{\pi}\), if and only if there exist \(v’ \in V’\) and \(v” \in V”\) such that \(v’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,…, V_k}\) of \(V(G)\) into independent sets such that \(V(H) = {v_1,v_2,…, 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\Box K_2\), it is shown that for every nontrivial connected graph \(H\) and every integer \(r \geq 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\Box K_2\) but that not all graphs \(H\) are homomorphic images of \(H\Box K_2\).