Pawel Rzazewski

ACM Trans. Algorithms, April, 2024

Towards the Chen-Raspaud conjecture.

[BibT_eX]

[DOI]

Katarzyna Lyczek

Maria Nazarczuk

Discret. Math., March, 2024

List Covering of Regular Multigraphs with Semi-edges.

[BibT_eX]

[DOI]

Algorithmica, March, 2024

Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree.

[BibT_eX]

[DOI]

J. Comb. Theory B, January, 2024

Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2024

Classifying subset feedback vertex set for H-free graphs.

[BibT_eX]

[DOI]

Giacomo Paesani

Daniël Paulusma

Theor. Comput. Sci., 2024

Induced Subgraphs of Bounded Treewidth and the Container Method.

[BibT_eX]

[DOI]

SIAM J. Comput., 2024

Coloring squares of planar graphs with small maximum degree.

[BibT_eX]

[DOI]

Mateusz Krzyzinski

Szymon Tur

Discuss. Math. Graph Theory, 2024

Maximum Partial List H-Coloring on P5-free graphs in polynomial time.

[BibT_eX]

[DOI]

CoRR, 2024

An 11/6-Approximation Algorithm for Vertex Cover on String Graphs.

[BibT_eX]

[DOI]

CoRR, 2024

Polynomial-time recognition and maximum independent set in Burling graphs.

[BibT_eX]

[DOI]

Bartosz Walczak

CoRR, 2024

Odd Cycle Transversal on P5-free Graphs in Polynomial Time.

[BibT_eX]

[DOI]

CoRR, 2024

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Max Weight Independent Set in Sparse Graphs with No Long Claws.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Sparse induced subgraphs in P6-free graphs.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes.

[BibT_eX]

[DOI]

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Tree Decompositions Meet Induced Matchings: Beyond Max Weight Independent Set.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

List Homomorphisms by Deleting Edges and Vertices: Tight Complexity Bounds for Bounded-Treewidth Graphs.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

Clique-width: Harnessing the power of atoms.

[BibT_eX]

[DOI]

J. Graph Theory, December, 2023

Completeness for the Complexity Class $\forall \exists \mathbb {R}$ and Area-Universality.

[BibT_eX]

[DOI]

Discret. Comput. Geom., July, 2023

Complexity of Ck-coloring in hereditary classes of graphs.

[BibT_eX]

[DOI]

Inf. Comput., June, 2023

Parameterized Inapproximability of Independent Set in H-Free Graphs.

[BibT_eX]

[DOI]

Pavel Dvorák

Andreas Emil Feldmann

Ashutosh Rai

Algorithmica, April, 2023

Sparsification Lower Bounds for List H-Coloring.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2023

Every graph is eventually Turán-good.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2023

Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Rank Parameters.

[BibT_eX]

[DOI]

CoRR, 2023

A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number.

[BibT_eX]

[DOI]

Marcin Pilipczuk

CoRR, 2023

Sparse induced subgraphs in P_6-free graphs.

[BibT_eX]

[DOI]

CoRR, 2023

Coloring and Recognizing Directed Interval Graphs.

[BibT_eX]

[DOI]

Grzegorz Gutowski

CoRR, 2023

Coloring and Recognizing Mixed Interval Graphs.

[BibT_eX]

[DOI]

Grzegorz Gutowski

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

2022

Packing Directed Cycles Quarter- and Half-Integrally.

[BibT_eX]

[DOI]

Comb., December, 2022

Faster 3-Coloring of Small-Diameter Graphs.

[BibT_eX]

[DOI]

Marta Piecyk

SIAM J. Discret. Math., September, 2022

Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs.

[BibT_eX]

[DOI]

Giacomo Paesani

Daniël Paulusma

SIAM J. Discret. Math., 2022

Constant Congestion Brambles in Directed Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2022

Degeneracy of Pt-free and C⩾t-free graphs with no large complete bipartite subgraphs.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2022

Tree decompositions with bounded independence number: beyond independent sets.

[BibT_eX]

[DOI]

Martin Milanic

CoRR, 2022

Exact and Approximation Algorithms for Sensor Placement Against DDoS Attacks.

[BibT_eX]

[DOI]

Dariusz Nogalski

Int. J. Appl. Math. Comput. Sci., 2022

Computing List Homomorphisms in Geometric Intersection Graphs.

[BibT_eX]

[DOI]

Sándor Kisfaludi-Bak

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022

Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

List Covering of Regular Multigraphs.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 33rd International Workshop, 2022

List Locally Surjective Homomorphisms in Hereditary Graph Classes.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

Taming Graphs with No Large Creatures and Skinny Ladders.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Finding Large H-Colorable Subgraphs in Hereditary Graph Classes.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2021

Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs.

[BibT_eX]

[DOI]

J. ACM, 2021

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.

[BibT_eX]

[DOI]

Algorithmica, 2021

Finding large induced sparse subgraphs in c>t -free graphs in quasipolynomial time.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth.

[BibT_eX]

[DOI]

Marta Piecyk

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Complexity of the List Homomorphism Problem in Hereditary Graph Classes.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Quasi-polynomial-time algorithm for Independent Set in Pt-free graphs via shrinking the space of induced paths.

[BibT_eX]

[DOI]

Marcin Pilipczuk

Michal Pilipczuk

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

2020

Subexponential algorithms for variants of the homomorphism problem in string graphs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2020

Designing RNA Secondary Structures Is Hard.

[BibT_eX]

[DOI]

Florian Sikora

J. Comput. Biol., 2020

Complete colourings of hypergraphs.

[BibT_eX]

[DOI]

Keith Edwards

Discret. Math., 2020

L(2, 1)-labeling of disk intersection graphs.

[BibT_eX]

[DOI]

Joanna Sokól

Discret. Appl. Math., 2020

Quasi-polynomial-time algorithm for Independent Set in Pt-free and C>t-free graphs via shrinking the space of connecting subgraphs.

[BibT_eX]

[DOI]

Marcin Pilipczuk

Michal Pilipczuk

CoRR, 2020

On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest.

[BibT_eX]

[DOI]

Algorithmica, 2020

Sparsification Lower Bounds for List H-Coloring.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs.

[BibT_eX]

[DOI]

Marta Piecyk

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Finding small-width connected path decompositions in polynomial time.

[BibT_eX]

[DOI]

Dariusz Dereniowski

Dorota Osula

Theor. Comput. Sci., 2019

H-colouring Pt-free graphs in subexponential time.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2019

Optimality Program in Segment and String Graphs.

[BibT_eX]

[DOI]

Algorithmica, 2019

Representing Graphs and Hypergraphs by Touching Polygons in 3D.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing and Network Visualization - 27th International Symposium, 2019

Packing Directed Circuits Quarter-Integrally.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Complexity of Ck-Coloring in Hereditary Classes of Graphs.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Fixing improper colorings of graphs.

[BibT_eX]

[DOI]

Valentin Garnero

Pedro Montealegre

Theor. Comput. Sci., 2018

Online Coloring and L(2, 1)-Labeling of Unit Disk Intersection Graphs.

[BibT_eX]

[DOI]

Joanna Sokól

Krzysztof Wesek

SIAM J. Discret. Math., 2018

Fine-grained complexity of coloring unit disks and balls.

[BibT_eX]

[DOI]

J. Comput. Geom., 2018

Achromatic and Harmonious Colorings of Circulant Graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2018

Homothetic polygons and beyond: Maximal cliques in intersection graphs.

[BibT_eX]

[DOI]

Valentin E. Brimkov

Matthew Szczepankiewicz

Joshua Terhaar

Discret. Appl. Math., 2018

Intersecting edge distinguishing colorings of hypergraphs.

[BibT_eX]

[DOI]

CoRR, 2018

Complexity of Token Swapping and Its Variants.

[BibT_eX]

[DOI]

Tillmann Miltzow

Algorithmica, 2018

∀∃ℝ-Completeness and Area-Universality.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization.

[BibT_eX]

[DOI]

László Egri

Dániel Marx

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017

Erratum: Constructing Optimal k-Radius Sequences.

[BibT_eX]

[DOI]

J. Adrian Bondy

SIAM J. Discret. Math., 2017

Tight Euler tours in uniform hypergraphs - computational aspects.

[BibT_eX]

[DOI]

Pawel Naroski

Discret. Math. Theor. Comput. Sci., 2017

On edge intersection graphs of paths with 2 bends.

[BibT_eX]

[DOI]

Martin Pergel

Discret. Appl. Math., 2017

Sequences of radius k for complete bipartite graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2017

Parallel algorithms constructing the cell graph.

[BibT_eX]

[DOI]

Albert Wolant

Concurr. Comput. Pract. Exp., 2017

2016

Constructing Optimal k-Radius Sequences.

[BibT_eX]

[DOI]

J. Adrian Bondy

SIAM J. Discret. Math., 2016

2015

Harmonious and achromatic colorings of fragmentable hypergraphs.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2015

Fixing Improper Colorings of Graphs.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2015: Theory and Practice of Computer Science, 2015

Massively Parallel Construction of the Cell Graph.

[BibT_eX]

[DOI]

Albert Wolant

Proceedings of the Parallel Processing and Applied Mathematics, 2015

2014

Exact algorithm for graph homomorphism and locally injective graph homomorphism.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2014

An Exact Algorithm for the Generalized List T-Coloring Problem.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2014

Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique.

[BibT_eX]

[DOI]

Valentin E. Brimkov

Matthew Szczepankiewicz

Joshua Terhaar

CoRR, 2014

Improving High-Performance GPU Graph Traversal with Compression.

[BibT_eX]

[DOI]

Piotr Przymus

Proceedings of the New Trends in Database and Information Systems II, 2014

2013

Fast exact algorithm for L(2, 1)-labeling of graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Determining the L(2, 1)L(2, 1)-span in polynomial space.

[BibT_eX]

[DOI]

Jan Kratochvíl

Discret. Appl. Math., 2013

2012

On the number of 2-packings in a connected graph.

[BibT_eX]

[DOI]

Discret. Math., 2012

Determining the L(2, 1)-Span in Polynomial Space.

[BibT_eX]

[DOI]

Jan Kratochvíl

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

Beyond Homothetic Polygons: Recognition and Maximum Clique.

[BibT_eX]

[DOI]

Jan Kratochvíl

Martin Pergel

Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Thrust and CUDA in Data Intensive Algorithms.

[BibT_eX]

[DOI]

Proceedings of the New Trends in Databases and Information Systems, 2012

2011

On the complexity of exact algorithm for L(2, 1)-labeling of graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2011

Determining L(2,1)-Span in Polynomial Space

[BibT_eX]

[DOI]

CoRR, 2011

Fast Exact Algorithm for L(2, 1)-Labeling of Graphs.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 2011

2010

On Improved Exact Algorithms for L(2, 1)-Labeling of Graphs.

[BibT_eX]

[DOI]