Critical sets for Sudoku and general graph colorings

DOI10.1016/j.disc.2013.10.011zbMath1279.05022arXiv1302.0318OpenAlexW2146221204MaRDI QIDQ393178

Anna Kirkpatrick, Joshua N. Cooper

Publication date: 16 January 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.0318

zbMATH Keywords

critical setminimum number of cluesSudoku

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15)

Related Items

Sudoku rectangle completion (extended abstract), Sudoku number of graphs

Uses Software

• SageMath

Cites Work

• Defining sets and uniqueness in graph colorings: A survey
• On the size of the minimum critical set of a Latin square
• On the computational complexity of defining sets
• There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration
• A superlinear lower bound for the size of a critical set in a latin square
• Computational Complexity
• Unnamed Item
• Unnamed Item