The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture Article Swipe
Ambroise Baril
,
Miguel Couceiro
,
Victor Lagerkvist
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2404.09798
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2404.09798
In this paper we are interested in the fine-grained complexity of deciding whether there is a homomorphism from an input graph $G$ to a fixed graph $H$ (the $H$-Coloring problem). The starting point is that these problems can be viewed as constraint satisfaction problems (CSPs), and that (partial) polymorphisms of binary relations are of paramount importance in the study of complexity classes of such CSPs. Thus, we first investigate the expressivity of binary symmetric relations $E_H$ and their corresponding (partial) polymorphisms pPol($E_H$). For irreflexive graphs we observe that there is no pair of graphs $H$ and $H'$ such that pPol($E_H$) $\subseteq$ pPol($E_{H'}$), unless $E_{H'}= \emptyset$ or $H =H'$. More generally we show the existence of an $n$-ary relation $R$ whose partial polymorphisms strictly subsume those of $H$ and such that CSP($R$) is NP-complete if and only if $H$ contains an odd cycle of length at most $n$. Motivated by this we also describe the sets of total polymorphisms of nontrivial cliques, odd cycles, as well as certain cores, and we give an algebraic characterization of projective cores. As a by-product, we settle the Okrasa and Rzążewski conjecture for all graphs of at most 7 vertices.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-212398
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4394707780
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4394707780Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2404.09798Digital Object Identifier
- Title
-
The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski ConjectureWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-04-15Full publication date if available
- Authors
-
Ambroise Baril, Miguel Couceiro, Victor LagerkvistList of authors in order
- Landing page
-
https://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-212398Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-212398Direct OA link when available
- Concepts
-
Homomorphism, Conjecture, Graph, Computer science, Combinatorics, Theoretical computer science, Discrete mathematics, MathematicsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4394707780 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2404.09798 |
| ids.doi | https://doi.org/10.48550/arxiv.2404.09798 |
| ids.openalex | https://openalex.org/W4394707780 |
| fwci | |
| type | preprint |
| title | The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| 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.9988999962806702 |
| 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.9976000189781189 |
| 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 | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C4042151 |
| concepts[0].level | 2 |
| concepts[0].score | 0.8750457763671875 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q215111 |
| concepts[0].display_name | Homomorphism |
| concepts[1].id | https://openalex.org/C2780990831 |
| concepts[1].level | 2 |
| concepts[1].score | 0.8345625996589661 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q319141 |
| concepts[1].display_name | Conjecture |
| concepts[2].id | https://openalex.org/C132525143 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5473466515541077 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[2].display_name | Graph |
| concepts[3].id | https://openalex.org/C41008148 |
| concepts[3].level | 0 |
| concepts[3].score | 0.5012426376342773 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[3].display_name | Computer science |
| concepts[4].id | https://openalex.org/C114614502 |
| concepts[4].level | 1 |
| concepts[4].score | 0.40908685326576233 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[4].display_name | Combinatorics |
| concepts[5].id | https://openalex.org/C80444323 |
| concepts[5].level | 1 |
| concepts[5].score | 0.398251473903656 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[5].display_name | Theoretical computer science |
| concepts[6].id | https://openalex.org/C118615104 |
| concepts[6].level | 1 |
| concepts[6].score | 0.37028610706329346 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[6].display_name | Discrete mathematics |
| concepts[7].id | https://openalex.org/C33923547 |
| concepts[7].level | 0 |
| concepts[7].score | 0.3610142469406128 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[7].display_name | Mathematics |
| keywords[0].id | https://openalex.org/keywords/homomorphism |
| keywords[0].score | 0.8750457763671875 |
| keywords[0].display_name | Homomorphism |
| keywords[1].id | https://openalex.org/keywords/conjecture |
| keywords[1].score | 0.8345625996589661 |
| keywords[1].display_name | Conjecture |
| keywords[2].id | https://openalex.org/keywords/graph |
| keywords[2].score | 0.5473466515541077 |
| keywords[2].display_name | Graph |
| keywords[3].id | https://openalex.org/keywords/computer-science |
| keywords[3].score | 0.5012426376342773 |
| keywords[3].display_name | Computer science |
| keywords[4].id | https://openalex.org/keywords/combinatorics |
| keywords[4].score | 0.40908685326576233 |
| keywords[4].display_name | Combinatorics |
| keywords[5].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[5].score | 0.398251473903656 |
| keywords[5].display_name | Theoretical computer science |
| keywords[6].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[6].score | 0.37028610706329346 |
| keywords[6].display_name | Discrete mathematics |
| keywords[7].id | https://openalex.org/keywords/mathematics |
| keywords[7].score | 0.3610142469406128 |
| keywords[7].display_name | Mathematics |
| language | en |
| locations[0].id | pmh:oai:DiVA.org:liu-212398 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400013 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Publications (Konstfack University of Arts, Crafts, and Design) |
| locations[0].source.host_organization | https://openalex.org/I218177685 |
| locations[0].source.host_organization_name | University College of Arts Crafts and Design |
| locations[0].source.host_organization_lineage | https://openalex.org/I218177685 |
| locations[0].license | other-oa |
| locations[0].pdf_url | |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | https://openalex.org/licenses/other-oa |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-212398 |
| locations[1].id | pmh:oai:HAL:hal-04536829v1 |
| locations[1].is_oa | False |
| locations[1].source.id | https://openalex.org/S4306402512 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | False |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | HAL (Le Centre pour la Communication Scientifique Directe) |
| locations[1].source.host_organization | https://openalex.org/I1294671590 |
| locations[1].source.host_organization_name | Centre National de la Recherche Scientifique |
| locations[1].source.host_organization_lineage | https://openalex.org/I1294671590 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | submittedVersion |
| locations[1].raw_type | Journal articles |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | False |
| locations[1].raw_source_name | Journal of Multiple-Valued Logic and Soft Computing, In press, ⟨10.48550/arXiv.2404.09798⟩ |
| locations[1].landing_page_url | https://hal.science/hal-04536829 |
| locations[2].id | doi:10.48550/arxiv.2404.09798 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S4306400194 |
| locations[2].source.issn | |
| locations[2].source.type | repository |
| locations[2].source.is_oa | True |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | arXiv (Cornell University) |
| locations[2].source.host_organization | https://openalex.org/I205783295 |
| locations[2].source.host_organization_name | Cornell University |
| locations[2].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[2].license | cc-by |
| locations[2].pdf_url | |
| locations[2].version | |
| locations[2].raw_type | article |
| locations[2].license_id | https://openalex.org/licenses/cc-by |
| locations[2].is_accepted | False |
| locations[2].is_published | |
| locations[2].raw_source_name | |
| locations[2].landing_page_url | https://doi.org/10.48550/arxiv.2404.09798 |
| indexed_in | datacite |
| authorships[0].author.id | https://openalex.org/A5078390607 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Ambroise Baril |
| authorships[0].affiliations[0].raw_affiliation_string | ORPAILLEUR - Knowledge representation, reasonning (France) |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Ambroise Baril |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | ORPAILLEUR - Knowledge representation, reasonning (France) |
| authorships[1].author.id | https://openalex.org/A5066732273 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-2316-7623 |
| authorships[1].author.display_name | Miguel Couceiro |
| authorships[1].countries | PT |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I121345201 |
| authorships[1].affiliations[0].raw_affiliation_string | INESC-ID - Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa (Rua Alves Redol 9 - Apartado 13069 - 1000-029 Lisboa - Portugal) |
| authorships[1].affiliations[1].raw_affiliation_string | ORPAILLEUR - Knowledge representation, reasonning (France) |
| authorships[1].institutions[0].id | https://openalex.org/I121345201 |
| authorships[1].institutions[0].ror | https://ror.org/04mqy3p58 |
| authorships[1].institutions[0].type | nonprofit |
| authorships[1].institutions[0].lineage | https://openalex.org/I121345201, https://openalex.org/I4210125590 |
| authorships[1].institutions[0].country_code | PT |
| authorships[1].institutions[0].display_name | Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Miguel Couceiro |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | INESC-ID - Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa (Rua Alves Redol 9 - Apartado 13069 - 1000-029 Lisboa - Portugal), ORPAILLEUR - Knowledge representation, reasonning (France) |
| authorships[2].author.id | https://openalex.org/A5089123758 |
| authorships[2].author.orcid | |
| authorships[2].author.display_name | Victor Lagerkvist |
| authorships[2].countries | SE |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I102134673 |
| authorships[2].affiliations[0].raw_affiliation_string | Linköpings Universitet = Linköping University (SE-58183 Linköping, Sweden - Sweden) |
| authorships[2].institutions[0].id | https://openalex.org/I102134673 |
| authorships[2].institutions[0].ror | https://ror.org/05ynxx418 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I102134673 |
| authorships[2].institutions[0].country_code | SE |
| authorships[2].institutions[0].display_name | Linköping University |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Victor Lagerkvist |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | Linköpings Universitet = Linköping University (SE-58183 Linköping, Sweden - Sweden) |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-212398 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| 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/W4391375266, https://openalex.org/W4308159138, https://openalex.org/W4327811209, https://openalex.org/W1979798674, https://openalex.org/W3169947911, https://openalex.org/W2914794208, https://openalex.org/W3037616202, https://openalex.org/W2963079901, https://openalex.org/W390508480, https://openalex.org/W2294450783 |
| cited_by_count | 0 |
| locations_count | 3 |
| best_oa_location.id | pmh:oai:DiVA.org:liu-212398 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400013 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Publications (Konstfack University of Arts, Crafts, and Design) |
| best_oa_location.source.host_organization | https://openalex.org/I218177685 |
| best_oa_location.source.host_organization_name | University College of Arts Crafts and Design |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I218177685 |
| best_oa_location.license | other-oa |
| best_oa_location.pdf_url | |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | https://openalex.org/licenses/other-oa |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-212398 |
| primary_location.id | pmh:oai:DiVA.org:liu-212398 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400013 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Publications (Konstfack University of Arts, Crafts, and Design) |
| primary_location.source.host_organization | https://openalex.org/I218177685 |
| primary_location.source.host_organization_name | University College of Arts Crafts and Design |
| primary_location.source.host_organization_lineage | https://openalex.org/I218177685 |
| primary_location.license | other-oa |
| primary_location.pdf_url | |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | https://openalex.org/licenses/other-oa |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-212398 |
| publication_date | 2024-04-15 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.7 | 193 |
| abstract_inverted_index.a | 15, 23, 178 |
| abstract_inverted_index.$H | 106 |
| abstract_inverted_index.As | 177 |
| abstract_inverted_index.In | 0 |
| abstract_inverted_index.an | 18, 115, 139, 171 |
| abstract_inverted_index.as | 40, 163, 165 |
| abstract_inverted_index.at | 144, 191 |
| abstract_inverted_index.be | 38 |
| abstract_inverted_index.by | 148 |
| abstract_inverted_index.if | 133, 136 |
| abstract_inverted_index.in | 6, 56 |
| abstract_inverted_index.is | 14, 33, 89, 131 |
| abstract_inverted_index.no | 90 |
| abstract_inverted_index.of | 10, 49, 53, 59, 62, 71, 92, 114, 125, 142, 155, 158, 174, 190 |
| abstract_inverted_index.or | 105 |
| abstract_inverted_index.to | 22 |
| abstract_inverted_index.we | 3, 66, 85, 110, 150, 169, 180 |
| abstract_inverted_index.$G$ | 21 |
| abstract_inverted_index.$H$ | 26, 94, 126, 137 |
| abstract_inverted_index.$R$ | 118 |
| abstract_inverted_index.For | 82 |
| abstract_inverted_index.The | 30 |
| abstract_inverted_index.all | 188 |
| abstract_inverted_index.and | 45, 76, 95, 127, 134, 168, 184 |
| abstract_inverted_index.are | 4, 52 |
| abstract_inverted_index.can | 37 |
| abstract_inverted_index.for | 187 |
| abstract_inverted_index.odd | 140, 161 |
| abstract_inverted_index.the | 7, 57, 69, 112, 153, 182 |
| abstract_inverted_index.$H'$ | 96 |
| abstract_inverted_index.$n$. | 146 |
| abstract_inverted_index.(the | 27 |
| abstract_inverted_index.More | 108 |
| abstract_inverted_index.also | 151 |
| abstract_inverted_index.from | 17 |
| abstract_inverted_index.give | 170 |
| abstract_inverted_index.most | 145, 192 |
| abstract_inverted_index.only | 135 |
| abstract_inverted_index.pair | 91 |
| abstract_inverted_index.sets | 154 |
| abstract_inverted_index.show | 111 |
| abstract_inverted_index.such | 63, 97, 128 |
| abstract_inverted_index.that | 34, 46, 87, 98, 129 |
| abstract_inverted_index.this | 1, 149 |
| abstract_inverted_index.well | 164 |
| abstract_inverted_index.$E_H$ | 75 |
| abstract_inverted_index.=H'$. | 107 |
| abstract_inverted_index.CSPs. | 64 |
| abstract_inverted_index.Thus, | 65 |
| abstract_inverted_index.cycle | 141 |
| abstract_inverted_index.first | 67 |
| abstract_inverted_index.fixed | 24 |
| abstract_inverted_index.graph | 20, 25 |
| abstract_inverted_index.input | 19 |
| abstract_inverted_index.paper | 2 |
| abstract_inverted_index.point | 32 |
| abstract_inverted_index.study | 58 |
| abstract_inverted_index.their | 77 |
| abstract_inverted_index.there | 13, 88 |
| abstract_inverted_index.these | 35 |
| abstract_inverted_index.those | 124 |
| abstract_inverted_index.total | 156 |
| abstract_inverted_index.whose | 119 |
| abstract_inverted_index.Okrasa | 183 |
| abstract_inverted_index.binary | 50, 72 |
| abstract_inverted_index.cores, | 167 |
| abstract_inverted_index.cores. | 176 |
| abstract_inverted_index.graphs | 84, 93, 189 |
| abstract_inverted_index.length | 143 |
| abstract_inverted_index.settle | 181 |
| abstract_inverted_index.unless | 102 |
| abstract_inverted_index.viewed | 39 |
| abstract_inverted_index.$n$-ary | 116 |
| abstract_inverted_index.(CSPs), | 44 |
| abstract_inverted_index.certain | 166 |
| abstract_inverted_index.classes | 61 |
| abstract_inverted_index.cycles, | 162 |
| abstract_inverted_index.observe | 86 |
| abstract_inverted_index.partial | 120 |
| abstract_inverted_index.subsume | 123 |
| abstract_inverted_index.whether | 12 |
| abstract_inverted_index.$E_{H'}= | 103 |
| abstract_inverted_index.CSP($R$) | 130 |
| abstract_inverted_index.cliques, | 160 |
| abstract_inverted_index.contains | 138 |
| abstract_inverted_index.deciding | 11 |
| abstract_inverted_index.describe | 152 |
| abstract_inverted_index.problems | 36, 43 |
| abstract_inverted_index.relation | 117 |
| abstract_inverted_index.starting | 31 |
| abstract_inverted_index.strictly | 122 |
| abstract_inverted_index.(partial) | 47, 79 |
| abstract_inverted_index.Motivated | 147 |
| abstract_inverted_index.algebraic | 172 |
| abstract_inverted_index.existence | 113 |
| abstract_inverted_index.generally | 109 |
| abstract_inverted_index.paramount | 54 |
| abstract_inverted_index.problem). | 29 |
| abstract_inverted_index.relations | 51, 74 |
| abstract_inverted_index.symmetric | 73 |
| abstract_inverted_index.vertices. | 194 |
| abstract_inverted_index.\emptyset$ | 104 |
| abstract_inverted_index.complexity | 9, 60 |
| abstract_inverted_index.conjecture | 186 |
| abstract_inverted_index.constraint | 41 |
| abstract_inverted_index.importance | 55 |
| abstract_inverted_index.interested | 5 |
| abstract_inverted_index.nontrivial | 159 |
| abstract_inverted_index.projective | 175 |
| abstract_inverted_index.$\subseteq$ | 100 |
| abstract_inverted_index.NP-complete | 132 |
| abstract_inverted_index.Rzążewski | 185 |
| abstract_inverted_index.by-product, | 179 |
| abstract_inverted_index.investigate | 68 |
| abstract_inverted_index.irreflexive | 83 |
| abstract_inverted_index.pPol($E_H$) | 99 |
| abstract_inverted_index.$H$-Coloring | 28 |
| abstract_inverted_index.expressivity | 70 |
| abstract_inverted_index.fine-grained | 8 |
| abstract_inverted_index.homomorphism | 16 |
| abstract_inverted_index.pPol($E_H$). | 81 |
| abstract_inverted_index.satisfaction | 42 |
| abstract_inverted_index.corresponding | 78 |
| abstract_inverted_index.polymorphisms | 48, 80, 121, 157 |
| abstract_inverted_index.pPol($E_{H'}$), | 101 |
| abstract_inverted_index.characterization | 173 |
| cited_by_percentile_year | |
| countries_distinct_count | 2 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |