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 Kk. 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 S1-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.
|Number of pages||24|
|Journal||SIAM Journal on Discrete Mathematics|
|State||Published - 2020|
Bibliographical notePublisher Copyright:
© 2020 Society for Industrial and Applied Mathematics.
- Betti number
- Hajos construction
- Neighborhood complex
ASJC Scopus subject areas
- Mathematics (all)