| 词条 | Precoloring extension |
| 释义 |
In graph theory, precoloring extension is the problem of extending a graph coloring of a subset of the vertices of a graph, with a given set of colors, to a coloring of the whole graph that does not assign the same color to any two adjacent vertices. It has the usual graph coloring problem as a special case, in which the initially colored subset of vertices is empty; therefore, it is NP-complete. However, it is also NP-complete for some other classes of graphs on which the usual graph coloring problem is easier. For instance it is NP-complete on the rook's graphs, for which it corresponds to the problem of completing a partially filled-in Latin square.[1] Precoloring extension may be seen as a special case of list coloring, the problem of coloring a graph in which no vertices have been colored, but each vertex has an assigned list of available colors. To transform a precoloring extension problem into a list coloring problem, assign each uncolored vertex in the precoloring extension problem a list of the colors not yet used by its initially-colored neighbors, and then remove the colored vertices from the graph. Sudoku puzzles may be modeled mathematically as instances of the precoloring extension problem on Sudoku graphs.[2]References1. ^{{citation | last = Colbourn | first = Charles J. | doi = 10.1016/0166-218X(84)90075-1 | issue = 1 | journal = Discrete Applied Mathematics | mr = 739595 | pages = 25–30 | title = The complexity of completing partial Latin squares | volume = 8 | year = 1984}}. 2. ^{{citation | last1 = Herzberg | first1 = Agnes M. | author1-link = Agnes M. Herzberg | last2 = Murty | first2 = M. Ram | author2-link = M. Ram Murty | issue = 6 | journal = Notices of the American Mathematical Society | mr = 2327972 | pages = 708–717 | title = Sudoku squares and chromatic polynomials | volume = 54 | year = 2007}} External links
1 : Graph coloring |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。