Partial Chromatic Polynomials and Diagonally Distinct Sudoku Squares

arXiv0804.0284MaRDI QIDQ6208975FDOQ6208975

Publication date: 1 April 2008

Abstract: Sudoku grids can be thought of as graphs where the vertices are the squares of the grid, and edges join vertices in the same row, column, or sub-grid. A Sudoku puzzle corresponds to a partial proper coloring of the Sudoku graph. We provide a new and simpler proof of the theorem which states that the number of completions of partial colorings of a graph is a polynomial in the number of colors (originally due to Herzberg and Murty). Moreover, we construct Sudoku squares of arbitrary size with distinct entries on both diagonals (a similar proof was first published by Keedwell, unknown to the author).

This page was built for publication: Partial Chromatic Polynomials and Diagonally Distinct Sudoku Squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6208975)