On avoiding some families of arrays

详细信息    查看全文

• 作者：Carl Johan Casselgren ^{carl-johan.casselgren@math.umu.se cj.casselgren@gmail.com}
• 关键词：Latin square ; Avoiding arrays ; List coloring
• 刊名：Discrete Mathematics
• 出版年：2012
• 出版时间：6 March, 2012
• 年：2012
• 卷：312
• 期：5
• 页码：963-972
• 全文大小：248 K

文摘

An array with entries from is avoidable if there is an Latin square such that no cell in contains a symbol that occurs in the corresponding cell in . We show that the problem of determining whether an array that contains at most two entries per cell is avoidable is -complete, even in the case when the array has entries from only two distinct symbols. Assuming that , this disproves a conjecture by ?hman. Furthermore, we present several new families of avoidable arrays. In particular, every single entry array (arrays where each cell contains at most one symbol) of order with entries from at most distinct symbols and where each symbol occurs in at most cells is avoidable, and every single entry array of order , where each of the symbols occurs in at most cells, is avoidable. Additionally, if , then every single entry array of order at least , where at most rows contain non-empty cells and where each symbol occurs in at most cells, is avoidable.