Forbidding subdivisions and line graphs towards faster algorithms

2022/45/N/ST6/04232

Keywords

Descriptors

  • ST6_006: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST1_014: Matematyka dyskretna i kombinatoryka

Panel

ST6 – Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

Voivodeship: mazowieckie

Other projects carried out by the institution »

Principal investigator (from the host institution)

Jana Masaříková

Number of co-investigators in the project: 2

Call

PRELUDIUM 21 – announced on 2022-03-28

Amount awarded
81 600 PLN
Project start date
2023-08-14
Project end date
2026-08-13
Project duration
36 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

Articles in post-conference publications (2)

  1. Path Eccentricity and Forbidden Induced Subgraphs

    Authors:
    Sylwia Cichacz, Claire Hilaire, Tomáš Masařík, Jana Masaříková, Martin Milanič
    Conference:
    Proceedings of EUROCOMB'25: European Conference on Combinatorics, Graph Theory and Applications (year: 2025, volume: EUROCOMB'25: European Conference on Combinatorics, Graph Theory and Applications, pages: 318-325), Publisher: HUN-REN Alfréd Rényi Insitute of Mathematics
    Date:
    conference August 25-29, 2025
    Status:
    Published
    DOI:
    10.48550/arXiv.2503.15747 – link to the publication
  2. Graphs with No Long Claws: An Improved Bound for the Analog of the Gyárfás' Path Argument

    Authors:
    Jana Masaříková, Wojciech Nadara, Marcin Pilipczuk
    Conference:
    50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) (year: 2025, volume: 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), pages: 28:1--28:16), Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
    Date:
    conference August 25-29, 2025
    Status:
    Published
    DOI:
    10.4230/LIPICS.MFCS.2025.28 – link to the publication

« New search

Graphic design and implementation: Jakub Piotrowski