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 games on graphs and partially ordered sets

2011/03/B/ST6/01367

Keywords:

poset on-line algorithm First-Fit coloring comparability graph Dilworth's theorem Ramsey's theorem

Descriptors:

  • ST6_7: Artificial intelligence, intelligent systems, multi-agent systems
  • ST1_15: Mathematical aspects of computer science
  • ST1_14: Discrete mathematics and combinatorics

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):

prof. Jarosław Grytczuk 

Number of co-investigators in the project: 5

Call: OPUS 2 - announced on 2011-09-15

Amount awarded: 585 000 PLN

Project start date (Y-m-d): 2012-08-28

Project end date (Y-m-d): 2015-05-27

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

Project status: Project settled

Information in the final report

  • Publication in academic press/journals (8)
  • Articles in post-conference publications (2)
  1. Fractional and j-fold colouring of the plane
    Authors:
    Jarosław Grytczuk, Konstanty Junosza-Szaniawski, Joanna Sokół, Krzysztof Węsek
    Academic press:
    Discrete and Computational Geometry (rok: 2016, tom: 55, strony: 594–609), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00454-016-9769-3 - link to the publication
  2. On-line approach to off-line coloring problems on graphs with geometric representations
    Authors:
    Tomasz Krawczyk, Bartosz Walczak
    Academic press:
    Combinatorica (rok: 2016, ), Wydawca: Springer
    Status:
    Accepted for publication
    DOI:
    10.1007/s00493-016-3414-x - link to the publication
  3. How to play Thue games
    Authors:
    Jarosław Grytczuk, Karol Kosiński, Michał Zmarz
    Academic press:
    Teoretical Computer Science (rok: 2015, tom: 582, strony: 2015), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2015.03.036 - link to the publication
  4. Triangle-free geometric intersection graphs with no large independent sets
    Authors:
    Bartosz Walczak
    Academic press:
    Discrete and Computational Geometry (rok: 2015, tom: 53, strony: 221-225), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00454-014-9645-y - link to the publication
  5. A lazy approach to on-line bipartite matching
    Authors:
    Jakub Kozik, Grzegorz Matecki
    Academic press:
    Algorithmica (rok: 2016, ), Wydawca: Springer
    Status:
    Submitted
    DOI:
    brak - link to the publication
  6. Additive coloring of planar graphs
    Authors:
    Tomasz Bartnicki, Bartłomiej Bosek, Sebastian Czerwiński, Jarosław Grytczuk, Grzegorz Matecki, Wiktor Żelazny
    Academic press:
    Graphs and Combinatorics (rok: 2014, tom: 30, strony: 1087-1098), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00373-013-1331-y - link to the publication
  7. On the Duality of Semiantichains and Unichain Coverings
    Authors:
    Bartłomiej Bosek, Stefan Felsner, Kolja Knauer, Grzegorz Matecki
    Academic press:
    Order (rok: 2016, tom: 33, strony: 29-38), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s11083-015-9348-x - link to the publication
  8. An Improved Subexponential Bound for On-line Chain Partitioning
    Authors:
    Bartłomiej Bosek, Hal A. Kierstead, Tomasz Krawczyk, Grzegorz Matecki, Matthew E. Smith
    Academic press:
    Journal of Combinatorial Theory, Series A (rok: 2015, tom: brak, strony: brak), Wydawca: Elsevier
    Status:
    Submitted
    DOI:
    brak - link to the publication
  1. Coloring relatives of interval overlap graphs via on-line games
    Authors:
    Tomasz Krawczyk, Bartosz Walczak
    Conference:
    41International Colloquium on Automata, Languages, and Programming (ICALP 2014) (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja 7-11.07.2014
    Status:
    Published
    DOI:
    link to the publication
  2. Asymmetric coloring games on incomparability graphs
    Authors:
    Tomasz Krawczyk, Bartosz Walczak
    Conference:
    EuroComb 2015 (rok: 2015, ), Wydawca: Lecture Notes in Discrete Mathematics
    Data:
    konferencja 31.08.2015-4.09.2015
    Status:
    Published
    DOI:
    link to the publication

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy