|
Description: |
Each partial coloring of a vertex subset W of a graph of order n defines a poset whose elements are minors. These minors are obtained by the contraction of edges such that the end-vertices have the same color from an arbitrary vertex coloring of the complement of W. In each of these posets, applying the Möbius inversion formula, we are able to compute the number of proper chromatic extensions which is a polynomial of degree n on the number of colors. Some practical applications are presented, namely in several problems related with the Sudoku puzzle (the very popular puzzle among readers of magazines and newspaper). Some open problemas are also posted. Finally, the obtained results are extended to the determination of chromatic polynomials. This presentation is based in several results obtained in [A. M. Herzberg and M. R. Murty, "Sudoku Squares and Chromatic Polynomials," Vol. 54 Notices of the AMS, (2007): 708--717] and in chapter 19 of [D. M. Cardoso, J. Szymanski and M. Rostami, "Matemática Discreta: combinatória, teoria dos grafos e algoritmos," Escolar Editora, 2008].
|
