Critical sets for Sudoku and general graph colorings

DOI10.1016/J.DISC.2013.10.011zbMATH Open1279.05022arXiv1302.0318OpenAlexW2146221204MaRDI QIDQ393178FDOQ393178

Authors: Anna Kirkpatrick, Joshua Cooper 

Publication date: 16 January 2014

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

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.

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

Recommendations

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

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)

Cites Work

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

Cited In (5)

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

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)