Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Colorings, cliques, and independent sets in graph classes

2019/34/E/ST6/00443

Keywords:

graph coloring χ-boundedness maximum independent set P_t-free graphs geometric representations

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 :

Uniwersytet Jagielloński, Wydział Matematyki i Informatyki

woj. małopolskie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr hab. Bartosz Maria Walczak 

Number of co-investigators in the project: 5

Call: SONATA BIS 9 - announced on 2019-06-17

Amount awarded: 2 251 481 PLN

Project start date (Y-m-d): 2020-04-10

Project end date (Y-m-d): 2026-04-09

Project duration:: 72 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

  • Publication in academic press/journals (9)
  • Articles in post-conference publications (3)
  1. Degeneracy of P_t-free and C_(≥t)-free graphs with no large complete bipartite subgraphs
    Authors:
    Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk, Paweł Rzążewski, Stéphan Thomassé, Bartosz Walczak
    Academic press:
    Journal of Combinatorial Theory, Series B (rok: 2022, tom: 152, strony: 353-378), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.005 - link to the publication
  2. Separating polynomial χ-boundedness from χ-boundedness
    Authors:
    Marcin Briański, James Davies, Bartosz Walczak
    Academic press:
    Combinatorica (rok: 2023, tom: brak, strony: brak), Wydawca: Springer
    Status:
    Submitted
  3. Tight bound on treedepth in terms of pathwidth and longest path
    Authors:
    Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak
    Academic press:
    Combinatorica (rok: 2024, tom: 44, strony: 417-427), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00493-023-00077-w - link to the publication
  4. A solution to Ringel's circle problem
    Authors:
    James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
    Academic press:
    Journal of the European Mathematical Society (rok: 2022, tom: brak danych, strony: brak danych), Wydawca: EMS Press
    Status:
    Submitted
  5. A solution to Ringel's circle problem
    Authors:
    James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
    Academic press:
    Journal of the European Mathematical Society (rok: 2022, tom: brak danych, strony: brak danych), Wydawca: EMS Press
    Status:
    Submitted
  6. Degeneracy of P_t-free and C_(≥t)-free graphs with no large complete bipartite subgraphs
    Authors:
    Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk, Paweł Rzążewski, Stéphan Thomassé, Bartosz Walczak
    Academic press:
    Journal of Combinatorial Theory, Series B (rok: 2022, tom: 152, strony: 353-378), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.005 - link to the publication
  7. Separating polynomial χ-boundedness from χ-boundedness
    Authors:
    Marcin Briański, James Davies, Bartosz Walczak
    Academic press:
    Combinatorica (rok: 2024, tom: 44, strony: 45665), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00493-023-00054-3 - link to the publication
  8. Tight bound on treedepth in terms of pathwidth and longest path
    Authors:
    Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak
    Academic press:
    Combinatorica (rok: 2023, tom: brak danych, strony: brak danych), Wydawca: Springer
    Status:
    Submitted
  9. Degeneracy of P_t-free and C_(≥t)-free graphs with no large complete bipartite subgraphs
    Authors:
    Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk, Paweł Rzążewski, Stéphan Thomassé, Bartosz Walczak
    Academic press:
    Journal of Combinatorial Theory, Series B (rok: 2022, tom: 152, strony: 353-378), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.005 - link to the publication
  1. A solution to Ringel's circle problem
    Authors:
    James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
    Conference:
    38th International Symposium on Computational Geometry (SoCG 2022) (rok: 2022, tom: SoCG 2022, strony: 33:1-14), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
    Data:
    konferencja 7-10.06.2022
    Status:
    Published
    DOI:
    10.4230/LIPIcs.SoCG.2022.33 - link to the publication
  2. A solution to Ringel's circle problem
    Authors:
    James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
    Conference:
    38th International Symposium on Computational Geometry (SoCG 2022) (rok: 2022, tom: SoCG 2022, strony: 33:1-14), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
    Data:
    konferencja 7-10.06.2022
    Status:
    Published
    DOI:
    10.4230/LIPIcs.SoCG.2022.33 - link to the publication
  3. A solution to Ringel's circle problem
    Authors:
    James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
    Conference:
    38th International Symposium on Computational Geometry (SoCG 2022) (tom: SoCG 2022, strony: ), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
    Data:
    konferencja 7-10.06.2022
    Status:
    Accepted for publication

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy