Hajos-type constructions and neighborhood complexes

Benjamin Braun, Julianne Vega

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)2424-2447
Number of pages24
JournalSIAM Journal on Discrete Mathematics
Issue number4
StatePublished - 2020

Bibliographical note

Publisher Copyright:
© 2020 Society for Industrial and Applied Mathematics.


  • Betti number
  • Hajos construction
  • Neighborhood complex

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Hajos-type constructions and neighborhood complexes'. Together they form a unique fingerprint.

Cite this