Edge Weight Based Colouring and Matching in Inhomogenous Random Graphs
摘要
In this paper, we study edge weight based colouring and matching in a random graph G with non-uniform edge probabilities. We equip each edge of G with a deterministic weight from a given set and establish an upper bound on the cardinality of the weight set that ensures a proper induced colouring. Next we use a use a variant of the polynomial edge weight based testing method to search for a perfect matching in \(G.\) We make crucial use of a Schwartz-Zippel type estimate (obtained using the probabilistic method) for bounding the zero set of a homogenous finite field polynomial.