Combinatorial Nullstellensatz: With Applications to Graph Colouring
By: and
Sign Up Now!
Already a Member? Log In
You must be logged into Bookshare to access this title.
Learn about membership options,
or view our freely available titles.
- Synopsis
- Combinatorial Nullstellensatz is a novel theorem in algebra introduced by Noga Alon to tackle combinatorial problems in diverse areas of mathematics. This book focuses on the applications of this theorem to graph colouring. A key step in the applications of Combinatorial Nullstellensatz is to show that the coefficient of a certain monomial in the expansion of a polynomial is nonzero. The major part of the book concentrates on three methods for calculating the coefficients: Alon-Tarsi orientation: The task is to show that a graph has an orientation with given maximum out-degree and for which the number of even Eulerian sub-digraphs is different from the number of odd Eulerian sub-digraphs. In particular, this method is used to show that a graph whose edge set decomposes into a Hamilton cycle and vertex-disjoint triangles is 3-choosable, and that every planar graph has a matching whose deletion results in a 4-choosable graph. Interpolation formula for the coefficient: This method is in particular used to show that toroidal grids of even order are 3-choosable, r-edge colourable r-regular planar graphs are r-edge choosable, and complete graphs of order p+1, where p is a prime, are p-edge choosable. Coefficients as the permanents of matrices: This method is in particular used in the study of the list version of vertex-edge weighting and to show that every graph is (2,3)-choosable. It is suited as a reference book for a graduate course in mathematics.
- Copyright:
- 2022
Book Details
- Book Quality:
- Publisher Quality
- Book Size:
- 134 Pages
- ISBN-13:
- 9781000426694
- Related ISBNs:
- 9781003138679, 9780367686949, 9780367687014
- Publisher:
- CRC Press
- Date of Addition:
- 07/13/23
- Copyrighted By:
- Xuding Zhu and R. Balakrishnan
- Adult content:
- No
- Language:
- English
- Has Image Descriptions:
- No
- Categories:
- Nonfiction, Mathematics and Statistics
- Submitted By:
- Bookshare Staff
- Usage Restrictions:
- This is a copyrighted book.