The Packing Chromatic Number of the Infinite Square Grid is 15 Article Swipe
Bernardo Subercaseaux
,
Marijn J. H. Heule
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.1007/978-3-031-30823-9_20
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.1007/978-3-031-30823-9_20
A packing k -coloring is a natural variation on the standard notion of graph k -coloring, where vertices are assigned numbers from $$\{1, \ldots , k\}$$ , and any two vertices assigned a common color $$c \in \{1, \ldots , k\}$$ need to be at a distance greater than c (as opposed to 1, in standard graph colorings). Despite a sequence of incremental work, determining the packing chromatic number of the infinite square grid has remained an open problem since its introduction in 2002. We culminate the search by proving this number to be 15. We achieve this result by improving the best-known method for this problem by roughly two orders of magnitude. The most important technique to boost performance is a novel, surprisingly effective propositional encoding for packing colorings. Additionally, we developed an alternative symmetry breaking method. Since both new techniques are more complex than existing techniques for this problem, a verified approach is required to trust them. We include both techniques in a proof of unsatisfiability, reducing the trusted core to the correctness of the direct encoding.
Related Topics
Metadata
- Type
- book-chapter
- Language
- en
- Landing Page
- https://doi.org/10.1007/978-3-031-30823-9_20
- https://link.springer.com/content/pdf/10.1007/978-3-031-30823-9_20.pdf
- OA Status
- hybrid
- Cited By
- 10
- References
- 16
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4366677950
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4366677950Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1007/978-3-031-30823-9_20Digital Object Identifier
- Title
-
The Packing Chromatic Number of the Infinite Square Grid is 15Work title
- Type
-
book-chapterOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-01-01Full publication date if available
- Authors
-
Bernardo Subercaseaux, Marijn J. H. HeuleList of authors in order
- Landing page
-
https://doi.org/10.1007/978-3-031-30823-9_20Publisher landing page
- PDF URL
-
https://link.springer.com/content/pdf/10.1007/978-3-031-30823-9_20.pdfDirect link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
hybridOpen access status per OpenAlex
- OA URL
-
https://link.springer.com/content/pdf/10.1007/978-3-031-30823-9_20.pdfDirect OA link when available
- Concepts
-
Algorithm, Computer science, Artificial intelligenceTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
10Total citation count in OpenAlex
- Citations by year (recent)
-
2025: 1, 2024: 7, 2023: 2Per-year citation counts (last 5 years)
- References (count)
-
16Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4366677950 |
|---|---|
| doi | https://doi.org/10.1007/978-3-031-30823-9_20 |
| ids.doi | https://doi.org/10.1007/978-3-031-30823-9_20 |
| ids.openalex | https://openalex.org/W4366677950 |
| fwci | 12.14476561 |
| type | book-chapter |
| title | The Packing Chromatic Number of the Infinite Square Grid is 15 |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | 406 |
| biblio.first_page | 389 |
| topics[0].id | https://openalex.org/T10374 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9998000264167786 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1703 |
| topics[0].subfield.display_name | Computational Theory and Mathematics |
| topics[0].display_name | Advanced Graph Theory Research |
| topics[1].id | https://openalex.org/T11329 |
| topics[1].field.id | https://openalex.org/fields/26 |
| topics[1].field.display_name | Mathematics |
| topics[1].score | 0.9980999827384949 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2607 |
| topics[1].subfield.display_name | Discrete Mathematics and Combinatorics |
| topics[1].display_name | Limits and Structures in Graph Theory |
| topics[2].id | https://openalex.org/T12541 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9973000288009644 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1703 |
| topics[2].subfield.display_name | Computational Theory and Mathematics |
| topics[2].display_name | Graph Labeling and Dimension Problems |
| is_xpac | False |
| apc_list.value | 5000 |
| apc_list.currency | EUR |
| apc_list.value_usd | 5392 |
| apc_paid.value | 5000 |
| apc_paid.currency | EUR |
| apc_paid.value_usd | 5392 |
| concepts[0].id | https://openalex.org/C11413529 |
| concepts[0].level | 1 |
| concepts[0].score | 0.629006028175354 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[0].display_name | Algorithm |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.5171727538108826 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C154945302 |
| concepts[2].level | 1 |
| concepts[2].score | 0.34252405166625977 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[2].display_name | Artificial intelligence |
| keywords[0].id | https://openalex.org/keywords/algorithm |
| keywords[0].score | 0.629006028175354 |
| keywords[0].display_name | Algorithm |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.5171727538108826 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[2].score | 0.34252405166625977 |
| keywords[2].display_name | Artificial intelligence |
| language | en |
| locations[0].id | doi:10.1007/978-3-031-30823-9_20 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S106296714 |
| locations[0].source.issn | 0302-9743, 1611-3349 |
| locations[0].source.type | book series |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | 0302-9743 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Lecture notes in computer science |
| locations[0].source.host_organization | https://openalex.org/P4310319900 |
| locations[0].source.host_organization_name | Springer Science+Business Media |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310319900 |
| locations[0].license | cc-by |
| locations[0].pdf_url | https://link.springer.com/content/pdf/10.1007/978-3-031-30823-9_20.pdf |
| locations[0].version | publishedVersion |
| locations[0].raw_type | book-chapter |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | Lecture Notes in Computer Science |
| locations[0].landing_page_url | https://doi.org/10.1007/978-3-031-30823-9_20 |
| indexed_in | crossref |
| authorships[0].author.id | https://openalex.org/A5030108071 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-2295-1299 |
| authorships[0].author.display_name | Bernardo Subercaseaux |
| authorships[0].countries | US |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I74973139 |
| authorships[0].affiliations[0].raw_affiliation_string | Carnegie Mellon University, Pittsburgh, PA, 15203, USA |
| authorships[0].institutions[0].id | https://openalex.org/I74973139 |
| authorships[0].institutions[0].ror | https://ror.org/05x2bcf33 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I74973139 |
| authorships[0].institutions[0].country_code | US |
| authorships[0].institutions[0].display_name | Carnegie Mellon University |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Bernardo Subercaseaux |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | Carnegie Mellon University, Pittsburgh, PA, 15203, USA |
| authorships[1].author.id | https://openalex.org/A5025921874 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-5587-8801 |
| authorships[1].author.display_name | Marijn J. H. Heule |
| authorships[1].countries | US |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I74973139 |
| authorships[1].affiliations[0].raw_affiliation_string | Carnegie Mellon University, Pittsburgh, PA, 15203, USA |
| authorships[1].institutions[0].id | https://openalex.org/I74973139 |
| authorships[1].institutions[0].ror | https://ror.org/05x2bcf33 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I74973139 |
| authorships[1].institutions[0].country_code | US |
| authorships[1].institutions[0].display_name | Carnegie Mellon University |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Marijn J. H. Heule |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | Carnegie Mellon University, Pittsburgh, PA, 15203, USA |
| has_content.pdf | True |
| has_content.grobid_xml | True |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://link.springer.com/content/pdf/10.1007/978-3-031-30823-9_20.pdf |
| open_access.oa_status | hybrid |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | The Packing Chromatic Number of the Infinite Square Grid is 15 |
| has_fulltext | True |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T10374 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9998000264167786 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1703 |
| primary_topic.subfield.display_name | Computational Theory and Mathematics |
| primary_topic.display_name | Advanced Graph Theory Research |
| related_works | https://openalex.org/W2748952813, https://openalex.org/W2051487156, https://openalex.org/W2073681303, https://openalex.org/W2390279801, https://openalex.org/W2358668433, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W2382290278, https://openalex.org/W2350741829, https://openalex.org/W2530322880 |
| cited_by_count | 10 |
| counts_by_year[0].year | 2025 |
| counts_by_year[0].cited_by_count | 1 |
| counts_by_year[1].year | 2024 |
| counts_by_year[1].cited_by_count | 7 |
| counts_by_year[2].year | 2023 |
| counts_by_year[2].cited_by_count | 2 |
| locations_count | 1 |
| best_oa_location.id | doi:10.1007/978-3-031-30823-9_20 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S106296714 |
| best_oa_location.source.issn | 0302-9743, 1611-3349 |
| best_oa_location.source.type | book series |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | 0302-9743 |
| best_oa_location.source.is_core | True |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Lecture notes in computer science |
| best_oa_location.source.host_organization | https://openalex.org/P4310319900 |
| best_oa_location.source.host_organization_name | Springer Science+Business Media |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310319900 |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | https://link.springer.com/content/pdf/10.1007/978-3-031-30823-9_20.pdf |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | book-chapter |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | Lecture Notes in Computer Science |
| best_oa_location.landing_page_url | https://doi.org/10.1007/978-3-031-30823-9_20 |
| primary_location.id | doi:10.1007/978-3-031-30823-9_20 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S106296714 |
| primary_location.source.issn | 0302-9743, 1611-3349 |
| primary_location.source.type | book series |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | 0302-9743 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Lecture notes in computer science |
| primary_location.source.host_organization | https://openalex.org/P4310319900 |
| primary_location.source.host_organization_name | Springer Science+Business Media |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310319900 |
| primary_location.license | cc-by |
| primary_location.pdf_url | https://link.springer.com/content/pdf/10.1007/978-3-031-30823-9_20.pdf |
| primary_location.version | publishedVersion |
| primary_location.raw_type | book-chapter |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | Lecture Notes in Computer Science |
| primary_location.landing_page_url | https://doi.org/10.1007/978-3-031-30823-9_20 |
| publication_date | 2023-01-01 |
| publication_year | 2023 |
| referenced_works | https://openalex.org/W1656795039, https://openalex.org/W3017968798, https://openalex.org/W3185307588, https://openalex.org/W2954910840, https://openalex.org/W2119765243, https://openalex.org/W2027444730, https://openalex.org/W2797038806, https://openalex.org/W1496529478, https://openalex.org/W2017604542, https://openalex.org/W2021870295, https://openalex.org/W66855977, https://openalex.org/W2590872906, https://openalex.org/W3095853283, https://openalex.org/W2483722158, https://openalex.org/W2998943866, https://openalex.org/W4366677950 |
| referenced_works_count | 16 |
| abstract_inverted_index., | 25, 39, 52 |
| abstract_inverted_index.A | 1 |
| abstract_inverted_index.a | 6, 45, 72, 86, 148, 178, 191 |
| abstract_inverted_index.c | 76 |
| abstract_inverted_index.k | 3, 15 |
| abstract_inverted_index.1, | 80 |
| abstract_inverted_index.We | 111, 122, 186 |
| abstract_inverted_index.an | 103, 160 |
| abstract_inverted_index.at | 71 |
| abstract_inverted_index.be | 70, 120 |
| abstract_inverted_index.by | 115, 126, 134 |
| abstract_inverted_index.in | 81, 109, 190 |
| abstract_inverted_index.is | 5, 147, 181 |
| abstract_inverted_index.of | 13, 88, 96, 138, 193, 202 |
| abstract_inverted_index.on | 9 |
| abstract_inverted_index.to | 69, 79, 119, 144, 183, 199 |
| abstract_inverted_index.we | 158 |
| abstract_inverted_index.$$c | 48 |
| abstract_inverted_index.(as | 77 |
| abstract_inverted_index.15. | 121 |
| abstract_inverted_index.The | 140 |
| abstract_inverted_index.\in | 49 |
| abstract_inverted_index.and | 40 |
| abstract_inverted_index.any | 41 |
| abstract_inverted_index.are | 19, 169 |
| abstract_inverted_index.for | 131, 154, 175 |
| abstract_inverted_index.has | 101 |
| abstract_inverted_index.its | 107 |
| abstract_inverted_index.new | 167 |
| abstract_inverted_index.the | 10, 92, 97, 113, 128, 196, 200, 203 |
| abstract_inverted_index.two | 42, 136 |
| abstract_inverted_index.\{1, | 50 |
| abstract_inverted_index.both | 166, 188 |
| abstract_inverted_index.core | 198 |
| abstract_inverted_index.from | 22 |
| abstract_inverted_index.grid | 100 |
| abstract_inverted_index.more | 170 |
| abstract_inverted_index.most | 141 |
| abstract_inverted_index.need | 68 |
| abstract_inverted_index.open | 104 |
| abstract_inverted_index.than | 75, 172 |
| abstract_inverted_index.this | 117, 124, 132, 176 |
| abstract_inverted_index.2002. | 110 |
| abstract_inverted_index.Since | 165 |
| abstract_inverted_index.boost | 145 |
| abstract_inverted_index.color | 47 |
| abstract_inverted_index.graph | 14, 83 |
| abstract_inverted_index.k\}$$ | 26, 53 |
| abstract_inverted_index.proof | 192 |
| abstract_inverted_index.since | 106 |
| abstract_inverted_index.them. | 185 |
| abstract_inverted_index.trust | 184 |
| abstract_inverted_index.where | 17 |
| abstract_inverted_index.work, | 90 |
| abstract_inverted_index.$$\{1, | 23 |
| abstract_inverted_index.\ldots | 24, 51 |
| abstract_inverted_index.common | 46 |
| abstract_inverted_index.direct | 204 |
| abstract_inverted_index.method | 130 |
| abstract_inverted_index.notion | 12 |
| abstract_inverted_index.novel, | 149 |
| abstract_inverted_index.number | 95, 118 |
| abstract_inverted_index.orders | 137 |
| abstract_inverted_index.result | 125 |
| abstract_inverted_index.search | 114 |
| abstract_inverted_index.square | 99 |
| abstract_inverted_index.Despite | 85 |
| abstract_inverted_index.achieve | 123 |
| abstract_inverted_index.complex | 171 |
| abstract_inverted_index.greater | 74 |
| abstract_inverted_index.include | 187 |
| abstract_inverted_index.method. | 164 |
| abstract_inverted_index.natural | 7 |
| abstract_inverted_index.numbers | 21 |
| abstract_inverted_index.opposed | 78 |
| abstract_inverted_index.packing | 2, 93, 155 |
| abstract_inverted_index.problem | 105, 133 |
| abstract_inverted_index.proving | 116 |
| abstract_inverted_index.roughly | 135 |
| abstract_inverted_index.trusted | 197 |
| abstract_inverted_index.Abstract | 0 |
| abstract_inverted_index.approach | 180 |
| abstract_inverted_index.assigned | 20, 44 |
| abstract_inverted_index.breaking | 163 |
| abstract_inverted_index.distance | 73 |
| abstract_inverted_index.encoding | 153 |
| abstract_inverted_index.existing | 173 |
| abstract_inverted_index.infinite | 98 |
| abstract_inverted_index.problem, | 177 |
| abstract_inverted_index.reducing | 195 |
| abstract_inverted_index.remained | 102 |
| abstract_inverted_index.required | 182 |
| abstract_inverted_index.sequence | 87 |
| abstract_inverted_index.standard | 11, 82 |
| abstract_inverted_index.symmetry | 162 |
| abstract_inverted_index.verified | 179 |
| abstract_inverted_index.vertices | 18, 43 |
| abstract_inverted_index.-coloring | 4 |
| abstract_inverted_index.<mml:math | 27, 54 |
| abstract_inverted_index.chromatic | 94 |
| abstract_inverted_index.culminate | 112 |
| abstract_inverted_index.developed | 159 |
| abstract_inverted_index.effective | 151 |
| abstract_inverted_index.encoding. | 205 |
| abstract_inverted_index.important | 142 |
| abstract_inverted_index.improving | 127 |
| abstract_inverted_index.technique | 143 |
| abstract_inverted_index.variation | 8 |
| abstract_inverted_index.-coloring, | 16 |
| abstract_inverted_index.<mml:mrow> | 29, 56 |
| abstract_inverted_index.best-known | 129 |
| abstract_inverted_index.colorings. | 156 |
| abstract_inverted_index.magnitude. | 139 |
| abstract_inverted_index.techniques | 168, 174, 189 |
| abstract_inverted_index.</mml:math> | 38, 67 |
| abstract_inverted_index.</mml:mrow> | 37, 66 |
| abstract_inverted_index.alternative | 161 |
| abstract_inverted_index.colorings). | 84 |
| abstract_inverted_index.correctness | 201 |
| abstract_inverted_index.determining | 91 |
| abstract_inverted_index.incremental | 89 |
| abstract_inverted_index.performance | 146 |
| abstract_inverted_index.introduction | 108 |
| abstract_inverted_index.surprisingly | 150 |
| abstract_inverted_index.Additionally, | 157 |
| abstract_inverted_index.propositional | 152 |
| abstract_inverted_index.unsatisfiability, | 194 |
| abstract_inverted_index.<mml:mi>c</mml:mi> | 57 |
| abstract_inverted_index.<mml:mi>k</mml:mi> | 35, 64 |
| abstract_inverted_index.<mml:mn>1</mml:mn> | 31, 60 |
| abstract_inverted_index.<mml:mo>,</mml:mo> | 32, 34, 61, 63 |
| abstract_inverted_index.<mml:mo>{</mml:mo> | 30, 59 |
| abstract_inverted_index.<mml:mo>}</mml:mo> | 36, 65 |
| abstract_inverted_index.<mml:mo>…</mml:mo> | 33, 62 |
| abstract_inverted_index.<mml:mo>∈</mml:mo> | 58 |
| abstract_inverted_index.xmlns:mml="http://www.w3.org/1998/Math/MathML"> | 28, 55 |
| cited_by_percentile_year.max | 99 |
| cited_by_percentile_year.min | 91 |
| countries_distinct_count | 1 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile.value | 0.98709293 |
| citation_normalized_percentile.is_in_top_1_percent | True |
| citation_normalized_percentile.is_in_top_10_percent | True |