From Connectivity to Coloring
Document Type
Article
Publication Date
8-1-2017
Description
A vertex set U ⊂ 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 XVC-partition π = {V1, V2,..........Vn} of the vertex set V(G) of a connected graph G is a partition of V(G) such that every VJ ϵ n is a minimal cutset of G. For an MVC- partition π of G, the π-graph G of G has vertex set -n such that V, V" e n are adjacent in G if and only if there exist v ϵ V and vv ϵ E(G) such that v v ϵ E(G). Graphs that are π-graphs of cycles are characterized. A homomorphic image H of a graph G can be obtained from a partition π = {V1, V2,..........Vn} of V(G) into independent sets such that V(H) = {V1, V2,..........Vn} , where vi is adjacent to Vj if and only if some vertex of K is adjacent to some vertex of Vj in G. By investigating graphs H that are homomorphic images of the Cartesian product H □ K2, it is shown that for every nontrivial connected graph H and every integer r > 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 □ K2 but that not all graphs H are homomorphic images of HDK2.
Citation Information
Chartrand, Gary; Haynes, Teresa W.; Hedetniemi, Stephen T.; and Zhang, Ping. 2017. From Connectivity to Coloring. Journal of Combinatorial Mathematics and Combinatorial Computing. Vol.102 203-219. ISSN: 0835-3026