|
|||||
|
|
Graphs with full rank 3-color matrix and few 3-colorings |
|
| Authors: | Serguei Norine Jean-Sbastien Sereni |
| Institution: | aSchool of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332-0160, USA;bInstitute for Theoretical Computer Science (iti) and Department of Applied Mathematics (kam), Faculty of Mathematics and Physics, Charles University, Malostranské náměstí 25, 118 00 Prague 1, Czech Republic |
| Abstract: | We exhibit a counterexample to a conjecture of Thomassen stating that the number of distinct 3-colorings of every graph whose 3-color matrix has full column rank is superpolynomial in the number of vertices. |
| Keywords: | Graph Vertex coloring Vector space |
| 本文献已被 ScienceDirect 等数据库收录！ | |