On some coloring problems in grids

DOI10.1016/J.TCS.2012.10.046MaRDI QIDQ1939251zbMATH OpenOpenAlexFDO

Authors Marc Demange, Dominique De Werra

Publication date 4 March 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.10.046

zbMATH Keywords

complexitygrid graphslist coloringprecoloring extension

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 7055496
• Publication:4934399
• Hard coloring problems in low degree planar bipartite graphs
• NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
• The Complexity of Counting Colourings of Subgraphs of the Grid

Cited in

(15)

• A robust \(p\)-center problem under pressure to locate shelters in wildfire context
• Signed coloring of 2-dimensional grids
• Grid representations and the chromatic number
• Answering conjunctive queries with inequalities
• Open problems on graph coloring for special graph classes
• Properly charged coloring of two-dimensional arrays
• scientific article; zbMATH DE number 6002424 (Why is no real title available?)
• Rectangle-free colorings of extremely complex grids using 4 colors
• scientific article; zbMATH DE number 6930532 (Why is no real title available?)
• scientific article; zbMATH DE number 913024 (Why is no real title available?)
• A square-grid coloring problem
• A Facility Coloring Problem in 1-D
• On periodicity of perfect colorings of the infinite hexagonal and triangular grids
• The Complexity of Counting Colourings of Subgraphs of the Grid
• The complexity of grid coloring

This page was built for publication: On some coloring problems in grids

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