Hajos-type constructions and neighborhood complexes

Any graph G with chromatic number k can be obtained using a Hajos-type construction, i.e., by iteratively performing the Haj os merge and vertex identification operations on a sequence of graphs starting with K_k. Finding such constructions for a given graph or family of graphs is a challenging task. In this paper, we show that for a large class of Haj os merges and for any identification of a pair of vertices having distance at least five from each other, the resulting graph has an S¹-wedge summand in its neighborhood complex. Our results imply that for a bridgeless graph G with a highly connected neighborhood complex, the final step in a Hajos construction must be a vertex identification with vertices at short distance from each other. We investigate this restriction in detail. We also introduce two graph construction algorithms using Hajos-type operations. We discuss the results of computational experiments in which we investigate the rank of the first homology group of the neighborhood complexes of graphs generated using these algorithms.