Projects funded by the NCN
The graph homomorphism problem in structurally restricted classes
2022/45/N/ST6/00237
Keywords:
graph homomorphism graph coloring computational complexity parameterized complexity diameter
Descriptors:
- ST6_004:
- ST6_006:
- ST1_014:
Panel:
ST6 - Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems
Host institution :
Politechnika Warszawska
woj. mazowieckie
Principal investigator (from the host institution):
Number of co-investigators in the project: 2
Call: PRELUDIUM 21 - announced on 2022-03-28
Amount awarded: 111 020 PLN
Project start date (Y-m-d): 2023-01-25
Project end date (Y-m-d): 2026-01-24
Project duration:: 36 months (the same as in the proposal)
Project status: Pending project
Project description
Download the project description in a pdf file
Note - project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.
Information in the final report
- Articles in post-conference publications (3)
- Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix ParametersAuthors:Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, Paweł RzążewskiConference:51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia (rok: 2024, tom: 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), strony: 77:1-77:21), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum für InformatikData:konferencja 8.07.2024-12.07.2024Status:PublishedDOI:10.4230/LIPIcs.ICALP.2024.77 - link to the publication
- C_{2k+1}-Coloring of Bounded-Diameter GraphsAuthors:Marta PiecykConference:49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia (rok: 2024, tom: 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), strony: 78:1-78:15), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für InformatikData:konferencja 26.08.2024-30.08.2024Status:PublishedDOI:10.4230/LIPIcs.MFCS.2024.78 - link to the publication
- Graph Reconstruction with Connectivity QueriesAuthors:Kacper Kluk, Hoang La, Marta PiecykConference:Graph-Theoretic Concepts in Computer Science. 50th International Workshop, WG 2024, Gozd Martuljek, Slovenia, June 19–21, 2024, Revised Selected Papers (rok: 2024, tom: 50th International Workshop on Graph-Theoretic Concepts in Computer Science, strony: 343-357), Wydawca: SpringerData:konferencja 19.06.2024-21.06.2024Status:PublishedDOI:10.1007/978-3-031-75409-8\_24 - link to the publication