Algebraic matching theory (Q1804180)

Summary: The number of vertices missed by a maximum matching in a graph \(G\) is the multiplicity of zero as a root of the matchings polynomial \(\mu(G, x)\) of \(G\), and hence many results in matching theory can be expressed in terms of this multiplicity. Thus, if \(\text{mult}(\theta, G)\) denotes the multiplicity of \(\theta\) as a zero of \(\mu(G, x)\), then Gallai's lemma is equivalent to the assertion that if \(\text{mult}(\theta, G\backslash u)< \text{mult}(\theta, G)\) for each vertex \(u\) of \(G\), then \(\text{mult}(\theta, G)= 1\). This paper extends a number of results in matching theory to results concerning \(\text{mult}(\theta, G)\), where \(\theta\) is not necessarily zero. If \(P\) is a path in \(G\) then \(G\backslash P\) denotes the graph got by deleting the vertices of \(P\) from \(G\). We prove that \(\text{mult}(\theta, G\backslash P)\geq \text{mult}(\theta, G)- 1\), and we say \(P\) is \(\theta\)-essential when equality holds. We show that if all paths in \(G\) are \(\theta\)-essential, then \(\text{mult}(\theta, G)= 1\). We define \(G\) to be \(\theta\)-critical if all vertices in \(G\) are \(\theta\)- essential and \(\text{mult}(\theta, G)= 1\). We prove that if \(\text{mult}(\theta, G)= k\) then there is an induced subgraph \(H\) with exactly \(k\) \(\theta\)-critical components, and the vertices in \(G\backslash H\) are covered by \(k\) disjoint paths.