Fall colouring of bipartite graphs and cartesian products of graphs
The question of whether a graph can be partitioned into k k independent dominating sets, which is the same as having a fall k k -colouring , is considered. For k=3 k = 3 , it is shown that a graph G G can be partitioned into three independent dominating sets if and only if the cartesian product G?K2 G ? K 2 can be partitioned into three independent dominating sets. The graph K2 K 2 can be replaced by any graph H H such that there is a mapping f:Qn?H f : Q n ? H , where f f is a type-II graph homomorphism. The cartesian product of two trees is considered, as well as the complexity of partitioning a bipartite graph into three independent dominating sets, which is shown to be NP-complete. For other values of k k , iterated cartesian products are considered, leading to a result that shows for what values of k k the hypercubes can be partitioned into k k independent dominating sets.
fall colouring cartesian product hypercube indominable domatic partition idomatic partition idomatic number