Projekty finansowane przez NCN

Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Kolorowania, kliki i zbiory niezależne w klasach grafów

2019/34/E/ST6/00443

Słowa kluczowe:

kolorowanie grafów χ-ograniczoność maksymalny zbiór niezależny grafy P_t-wolne reprezentacje geometryczne

Deskryptory:

  • ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna, algorytmy kwantowe
  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST1_14: Matematyka dyskretna i kombinatoryka

Panel:

ST6 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne

Jednostka realizująca:

Uniwersytet Jagielloński, Wydział Matematyki i Informatyki

woj.

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

dr hab. Bartosz Maria Walczak 

Liczba wykonawców projektu: 5

Konkurs: SONATA BIS 9 - ogłoszony 2019-06-17

Przyznana kwota: 2 251 481 PLN

Rozpoczęcie projektu: 2020-04-10

Zakończenie projektu: 2025-04-09

Planowany czas trwania projektu: 60 miesięcy (z wniosku)

Status projektu: Projekt zakończony

Opis Projektu

Pobierz opis projektu w formacie .pdf

Uwaga - opisy projektów zostały sporządzone przez samych autorów wniosków i w niezmienionej formie umieszczone w systemie.

Dane z raportu końcowego/rocznego

  • Publikacje w czasopismach (9)
  • Teksty w publikacjach pokonferencyjnych (3)
  1. Degeneracy of P_t-free and C_(≥t)-free graphs with no large complete bipartite subgraphs
    Autorzy:
    Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk, Paweł Rzążewski, Stéphan Thomassé, Bartosz Walczak
    Czasopismo:
    Journal of Combinatorial Theory, Series B (rok: 2022, tom: 152, strony: 353-378), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.005 - link do publikacji
  2. Separating polynomial χ-boundedness from χ-boundedness
    Autorzy:
    Marcin Briański, James Davies, Bartosz Walczak
    Czasopismo:
    Combinatorica (rok: 2023, tom: brak, strony: brak), Wydawca: Springer
    Status:
    Złożona
  3. Tight bound on treedepth in terms of pathwidth and longest path
    Autorzy:
    Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak
    Czasopismo:
    Combinatorica (rok: 2024, tom: 44, strony: 417-427), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00493-023-00077-w - link do publikacji
  4. A solution to Ringel's circle problem
    Autorzy:
    James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
    Czasopismo:
    Journal of the European Mathematical Society (rok: 2022, tom: brak danych, strony: brak danych), Wydawca: EMS Press
    Status:
    Złożona
  5. A solution to Ringel's circle problem
    Autorzy:
    James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
    Czasopismo:
    Journal of the European Mathematical Society (rok: 2022, tom: brak danych, strony: brak danych), Wydawca: EMS Press
    Status:
    Złożona
  6. Degeneracy of P_t-free and C_(≥t)-free graphs with no large complete bipartite subgraphs
    Autorzy:
    Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk, Paweł Rzążewski, Stéphan Thomassé, Bartosz Walczak
    Czasopismo:
    Journal of Combinatorial Theory, Series B (rok: 2022, tom: 152, strony: 353-378), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.005 - link do publikacji
  7. Separating polynomial χ-boundedness from χ-boundedness
    Autorzy:
    Marcin Briański, James Davies, Bartosz Walczak
    Czasopismo:
    Combinatorica (rok: 2024, tom: 44, strony: 45665), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00493-023-00054-3 - link do publikacji
  8. Tight bound on treedepth in terms of pathwidth and longest path
    Autorzy:
    Meike Hatzel, Gwenaël Joret, Piotr Micek, Marcin Pilipczuk, Torsten Ueckerdt, Bartosz Walczak
    Czasopismo:
    Combinatorica (rok: 2023, tom: brak danych, strony: brak danych), Wydawca: Springer
    Status:
    Złożona
  9. Degeneracy of P_t-free and C_(≥t)-free graphs with no large complete bipartite subgraphs
    Autorzy:
    Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk, Paweł Rzążewski, Stéphan Thomassé, Bartosz Walczak
    Czasopismo:
    Journal of Combinatorial Theory, Series B (rok: 2022, tom: 152, strony: 353-378), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.005 - link do publikacji
  1. A solution to Ringel's circle problem
    Autorzy:
    James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
    Konferencja:
    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:
    Opublikowana
    Doi:
    10.4230/LIPIcs.SoCG.2022.33 - link do publikacji
  2. A solution to Ringel's circle problem
    Autorzy:
    James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
    Konferencja:
    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:
    Opublikowana
    Doi:
    10.4230/LIPIcs.SoCG.2022.33 - link do publikacji
  3. A solution to Ringel's circle problem
    Autorzy:
    James Davies, Chaya Keller, Linda Kleist, Shakhar Smorodinsky, Bartosz Walczak
    Konferencja:
    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:
    Przyjęta do publikacji

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy