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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Edge Weight Based Colouring and Matching in Inhomogenous Random Graphs

  • Ghurumuruhan Ganesan

摘要

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.