Collapsing unicolored graphs

Abstract A graph is said to be unicolored if it is colored by nonnegative integers so that adjacent points have colors that differ in absolute value by one. A unicolored graph is collapsible if it has a 1-factor that does not contain a 1-factor of any bicolored cycle. We show that a regular CW complex K cell collapses to a subcomplex O if and only if its relative unicolored incidence graph collapses. We consider the 1-factors and the bicolored cycles of unicolored incidence graphs and their relationship to the relative homology and homotopy properties of the pair of cell complexes.