Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Coloring geometric intersection graphs and related problems

2015/17/D/ST1/00585

Keywords:

discrete geometry geometric intersection graphs on-line algorithms

Descriptors:

  • ST1_14: Discrete mathematics and combinatorics
  • ST1_15: Mathematical aspects of computer science

Panel:

ST1 - Mathematics: all areas of mathematics, pure and applied, as well as mathematical foundations of computer science, physics and statistics

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 Walczak 

Number of co-investigators in the project: 2

Call: SONATA 9 - announced on 2015-03-16

Amount awarded: 185 000 PLN

Project start date (Y-m-d): 2016-01-28

Project end date (Y-m-d): 2019-09-27

Project duration:: 44 months (the same as in the proposal)

Project status: Project settled

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.

Equipment purchased [PL]

  1. Laptop (5 000 PLN)
  2. Prezenter bezprzewodowy.
  3. Przejściówka microHDMI/HDMI/VGA.

Information in the final report

  • Publication in academic press/journals (8)
  • Articles in post-conference publications (4)
  1. Common tangents of two disjoint polygons in linear time and constant workspace
    Authors:
    Mikkel Abrahamsen, Bartosz Walczak
    Academic press:
    ACM Transactions on Algorithms (rok: 2018, tom: 15, strony: 12:1-12:21), Wydawca: Association for Computing Machinery
    Status:
    Published
    DOI:
    10.1145/3284355 - link to the publication
  2. Clustered 3-colouring graphs of bounded degree
    Authors:
    Vida Dujmović, Louis Esperet, Pat Morin, Bartosz Walczak, David R. Wood
    Academic press:
    Combinatorics, Probability and Computing (rok: 2022, tom: 31, strony: 123-135), Wydawca: Cambridge University Press
    Status:
    Published
    DOI:
    10.1017/S0963548321000213 - link to the publication
  3. Outerstring graphs are χ-bounded
    Authors:
    Alexandre Rok, Bartosz Walczak
    Academic press:
    SIAM Journal on Discrete Mathematics (rok: 2019, tom: 33, strony: 2181-2199), Wydawca: Society for Industrial and Applied Mathematics
    Status:
    Published
    DOI:
    10.1137/17M1157374 - link to the publication
  4. Sparse Kneser graphs are Hamiltonian
    Authors:
    Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak
    Academic press:
    Journal of the London Mathematical Society (rok: 2021, tom: 103, strony: 1253-1275), Wydawca: London Mathematical Society
    Status:
    Published
    DOI:
    10.1112/jlms.12406 - link to the publication
  5. Planar graphs have bounded nonrepetitive chromatic number
    Authors:
    Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, David R. Wood
    Academic press:
    Advances in Combinatorics (rok: 2020, tom: 2020, strony: 5:1-11), Wydawca: Alliance of Diamond Open Access Journals
    Status:
    Published
    DOI:
    10.19086/aic.12100 - link to the publication
  6. Grounded L-graphs are polynomially χ-bounded
    Authors:
    James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak
    Academic press:
    Discrete and Computational Geometry (rok: 2021, ), Wydawca: Springer
    Status:
    Submitted
    DOI:
    brak - link to the publication
  7. Coloring triangle-free L-graphs with O(log log n) colors
    Authors:
    Bartosz Walczak
    Academic press:
    Acta Mathematica Universitatis Comenianae (rok: 2019, tom: 88, strony: 1063-1069), Wydawca: Comenius University
    Status:
    Published
    DOI:
    brak - link to the publication
  8. Coloring curves that cross a fixed curve
    Authors:
    Alexandre Rok, Bartosz Walczak
    Academic press:
    Discrete and Computational Geometry (rok: 2019, tom: 61, strony: 830-851), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00454-018-0031-z - link to the publication
  1. Colouring polygon visibility graphs and their generalizations
    Authors:
    James Davies, Tomasz Krawczyk, Rose McCarty, Bartosz Walczak
    Conference:
    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:
    Published
  2. Coloring curves that cross a fixed curve
    Authors:
    Alexandre Rok, Bartosz Walczak
    Conference:
    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:
    Published
  3. Coloring and maximum weight independent set of rectangles
    Authors:
    Parinya Chalermsook, Bartosz Walczak
    Conference:
    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:
    Published
  4. Sparse Kneser graphs are Hamiltonian
    Authors:
    Torsten Mütze, Jerri Nummenpalo, Bartosz Walczak
    Conference:
    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:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy