At most \(k\)-to-1 mappings between graphs. II (Q1918542)

Let \(f\) be a \((\leq k)\)-to-\(1\) function from the vertex set of a graph \(G\) onto the vertex set of a graph \(H\). The authors ask: when does \(f\) extend to a continuous \((\leq k)\)-to-\(1\) function from \(G\) onto \(H\)? In Part I [Contemporary methods in graph theory. In honour of Prof. Dr. K. Wagner, 383-398 (1990; Zbl 0715.05050)], they answer this question, for \(k\) odd, with local conditions on the adjacency matrix for \(H\) and on the inverse adjacency matrix for \(G\). The present paper considers \(k\) even; global conditions are required and are encapsulated in a matrix \(C\) that exists precisely when \(f\) extends. The entries of \(C\) describe how \(f\) is to be constructed. The authors show that one can determine if \(C\) exists in polynomial time.