The complexity of grid coloring

DOI10.1007/S00224-022-10098-5MaRDI QIDQ6109067zbMATH OpenOpenAlexFDO

Authors Daniel Apon, William Gasarch, Kevin Lawler

Publication date 26 July 2023

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://scholarworks.uark.edu/etd/108

zbMATH Keywords

gridcomplexitycoloring

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• The Complexity of Counting Colourings of Subgraphs of the Grid
• On some coloring problems in grids
• The complexity of some graph colouring problems
• scientific article; zbMATH DE number 2145230
• Colouring, constraint satisfaction, and complexity
• The complexity of colouring problems on dense graphs
• scientific article; zbMATH DE number 139777
• ON THE COMPLEXITY OF SOME COLORING GAMES

Cites work

• scientific article; zbMATH DE number 6930532 (Why is no real title available?)
• Ectremal binary matrices without constant 2-squares
• Finding squares and rectangles in sets of points
• On reductions of NP sets to sparse sets
• Recent progress in the Boolean domain
• Rectangle-free colorings of extremely complex grids using 4 colors
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis

Cited in

(4)

• ON THE COMPLEXITY OF SOME COLORING GAMES
• The Parallel Complexity of Coloring Games
• The algorithmic complexity of colour switching
• Oblivious complexity classes revisited: lower bounds and hierarchies

This page was built for publication: The complexity of grid coloring

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