Projekty finansowane przez NCN


Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Kolorowanie geometrycznych grafów przecięć i problemy pokrewne

2015/17/D/ST1/00585

Słowa kluczowe:

geometria dyskretna geometryczne grafy przecięć algorytmy on-line

Deskryptory:

  • ST1_14: Kombinatoryka
  • ST1_15: Matematyczne aspekty informatyki

Panel:

ST1 - Nauki matematyczne: wszystkie dziedziny matematyki, teoretyczne oraz stosowane a także podstawy matematyczne informatyki, fizyka matematyczna i statystyka matematyczna

Jednostka realizująca:

Uniwersytet Jagielloński, Wydział Matematyki i Informatyki

woj. małopolskie

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

dr hab. Bartosz Walczak 

Liczba wykonawców projektu: 2

Konkurs: SONATA 9 - ogłoszony 2015-03-16

Przyznana kwota: 185 000 PLN

Rozpoczęcie projektu: 2016-01-28

Zakończenie projektu: 2019-09-27

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

Status projektu: Projekt rozliczony

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

  • Publikacje w czasopismach (8)
  • Teksty w publikacjach pokonferencyjnych (4)
  1. Coloring curves that cross a fixed curve IF: 0,621
    Autorzy:
    Alexandre Rok, Bartosz Walczak
    Czasopismo:
    Discrete and Computational Geometry (rok: 2019, tom: 61, strony: 830-851), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00454-018-0031-z - link do publikacji
  2. Planar graphs have bounded nonrepetitive chromatic number
    Autorzy:
    Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, David R. Wood
    Czasopismo:
    Advances in Combinatorics (rok: 2020, tom: 2020, strony: 5:1-11), Wydawca: Alliance of Diamond Open Access Journals
    Status:
    Opublikowana
    Doi:
    10.19086/aic.12100 - link do publikacji
  3. Sparse Kneser graphs are Hamiltonian IF: 1,137
    Autorzy:
    Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak
    Czasopismo:
    Journal of the London Mathematical Society (rok: 2021, tom: 103, strony: 1253-1275), Wydawca: London Mathematical Society
    Status:
    Opublikowana
    Doi:
    10.1112/jlms.12406 - link do publikacji
  4. Coloring triangle-free L-graphs with O(log log n) colors
    Autorzy:
    Bartosz Walczak
    Czasopismo:
    Acta Mathematica Universitatis Comenianae (rok: 2019, tom: 88, strony: 1063-1069), Wydawca: Comenius University
    Status:
    Opublikowana
  5. Common tangents of two disjoint polygons in linear time and constant workspace IF: 0,817
    Autorzy:
    Mikkel Abrahamsen, Bartosz Walczak
    Czasopismo:
    ACM Transactions on Algorithms (rok: 2018, tom: 15, strony: 12:1-12:21), Wydawca: Association for Computing Machinery
    Status:
    Opublikowana
    Doi:
    10.1145/3284355 - link do publikacji
  6. Clustered 3-colouring graphs of bounded degree IF: 1,032
    Autorzy:
    Vida Dujmović, Louis Esperet, Pat Morin, Bartosz Walczak, David R. Wood
    Czasopismo:
    Combinatorics, Probability and Computing (rok: 2022, tom: 31, strony: 123-135), Wydawca: Cambridge University Press
    Status:
    Opublikowana
    Doi:
    10.1017/S0963548321000213 - link do publikacji
  7. Outerstring graphs are χ-bounded IF: 0,75
    Autorzy:
    Alexandre Rok, Bartosz Walczak
    Czasopismo:
    SIAM Journal on Discrete Mathematics (rok: 2019, tom: 33, strony: 2181-2199), Wydawca: Society for Industrial and Applied Mathematics
    Status:
    Opublikowana
    Doi:
    10.1137/17M1157374 - link do publikacji
  8. Grounded L-graphs are polynomially χ-bounded IF: 0,969
    Autorzy:
    James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak
    Czasopismo:
    Discrete and Computational Geometry (rok: 2021, ), Wydawca: Springer
    Status:
    Złożona
  1. Colouring polygon visibility graphs and their generalizations
    Autorzy:
    James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak
    Konferencja:
    37th International Symposium on Computational Geometry (SoCG 2021) (rok: 2021, ), Wydawca: Schloss Dagstuhl – Leibniz Zentrum für Informatik
    Data:
    konferencja 7-11.06.2021
    Status:
    Opublikowana
  2. Sparse Kneser graphs are Hamiltonian
    Autorzy:
    Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak
    Konferencja:
    50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC'18) (rok: 2018, ), Wydawca: Association for Computing Machinery
    Data:
    konferencja 25-29.06.2018
    Status:
    Opublikowana
  3. Coloring curves that cross a fixed curve
    Autorzy:
    Alexandre Rok, Bartosz Walczak
    Konferencja:
    33rd International Symposium on Computational Geometry (SoCG 2017) (rok: 2017, ), Wydawca: Schloss Dagstuhl – Leibniz Zentrum für Informatik
    Data:
    konferencja 4-7.07.2017
    Status:
    Opublikowana
  4. Coloring and maximum weight independent set of rectangles
    Autorzy:
    Parinya Chalermsook, Bartosz Walczak
    Konferencja:
    32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'21) (rok: 2021, ), Wydawca: Society of Industrial and Applied Mathematics
    Data:
    konferencja 10-13.01.2021
    Status:
    Opublikowana