Critical sets for Sudoku and general graph colorings

DOI10.1016/J.DISC.2013.10.011MaRDI QIDQ393178zbMATH OpenOpenAlexFDO

Authors Anna Kirkpatrick, Joshua 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)

Abstract: We discuss the problem of finding critical sets in graphs, a concept which has appeared in a number of guises in the combinatorics and graph theory literature. The case of the Sudoku graph receives particular attention, because critical sets correspond to minimal fair puzzles. We define four parameters associated with the sizes of extremal critical sets and (a) prove several general results about these parameters' properties, including their computational intractability, (b) compute their values exactly for some classes of graphs, (c) obtain bounds for generalized Sudoku graphs, and (d) offer a number of open questions regarding critical sets and the aforementioned parameters.

Recommendations

• A study of the Sudoku graph family
• scientific article; zbMATH DE number 5251073
• Sudoku number of graphs
• scientific article; zbMATH DE number 5356325
• scientific article; zbMATH DE number 1146235

Cites work

• scientific article; zbMATH DE number 2127501 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A superlinear lower bound for the size of a critical set in a latin square
• Computational Complexity
• Defining sets and uniqueness in graph colorings: A survey
• On the computational complexity of defining sets
• On the size of the minimum critical set of a Latin square
• There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration

Cited in

(5)

• A study of the Sudoku graph family
• Sudoku number of graphs
• Bounds and monotonicity of critical set parameters of colourings
• There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration
• Sudoku rectangle completion (extended abstract)

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Critical sets for Sudoku and general graph colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q393178)