Zdenek Dvorák

J. Comb. Theory B, 2025

Product Structure of Graph Classes with Strongly Sublinear Separators.

[BibT_eX]

[DOI]

David R. Wood

Innov. Graph Theory, 2025

Sparsity of 3-flow-critical graphs.

[BibT_eX]

[DOI]

Eur. J. Comb., 2025

Asymptotic dimension of intersection graphs.

[BibT_eX]

[DOI]

Eur. J. Comb., 2025

Precoloring extension in planar near-Eulerian-triangulations.

[BibT_eX]

[DOI]

Eur. J. Comb., 2025

2024

Solution to a Problem of Grünbaum on the Edge Density of 4-Critical Planar Graphs.

[BibT_eX]

[DOI]

Carl Feghali

Comb., August, 2024

Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations.

[BibT_eX]

[DOI]

J. Comb. Theory B, January, 2024

Weak diameter coloring of graphs on surfaces.

[BibT_eX]

[DOI]

Eur. J. Comb., 2024

Towards Characterization of 5-List-Colorability of Toroidal Graphs.

[BibT_eX]

[DOI]

Félix Moreno Peñarrubia

CoRR, 2024

A Strengthening and an Efficient Implementation of Alon-Tarsi List Coloring Method.

[BibT_eX]

[DOI]

Electron. J. Comb., 2024

2023

Induced odd cycle packing number, independent sets, and chromatic number.

[BibT_eX]

[DOI]

J. Graph Theory, July, 2023

On Density of $\boldsymbol{\mathbb{Z}_3}$ -Flow-Critical Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., June, 2023

A note on local search for hitting sets.

[BibT_eX]

[DOI]

CoRR, 2023

Embedded graph 3-coloring and flows.

[BibT_eX]

[DOI]

CoRR, 2023

An efficient implementation and a strengthening of Alon-Tarsi list coloring method.

[BibT_eX]

[DOI]

CoRR, 2023

Maximum Edge Colouring Problem On Graphs That Exclude a Fixed Minor.

[BibT_eX]

[DOI]

Abhiruk Lahiri

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

Representation of Short Distances in Structurally Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

2022

On Decidability of Hyperbolicity.

[BibT_eX]

[DOI]

Comb., December, 2022

Coloring count cones of planar graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2022

On weighted sublinear separators.

[BibT_eX]

[DOI]

J. Graph Theory, 2022

Triangle-free planar graphs with at most 64n0.731 3-colorings.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2022

Characterization of 4-critical triangle-free toroidal graphs.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2022

Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2022

Square roots of nearly planar graphs.

[BibT_eX]

[DOI]

Benjamin R. Moore

Abhiruk Lahiri

CoRR, 2022

Approximation Metatheorems for Classes with Bounded Expansion.

[BibT_eX]

[DOI]

Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

Weak Coloring Numbers of Intersection Graphs.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Computational Geometry, 2022

On Comparable Box Dimension.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

Sublinear Separators in Intersection Graphs of Convex Shapes.

[BibT_eX]

[DOI]

Rose McCarty

SIAM J. Discret. Math., 2021

Flexibility of triangle-free planar graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2021

Single-conflict colouring.

[BibT_eX]

[DOI]

J. Graph Theory, 2021

Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2021

Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2021

Coloring near-quadrangulations of the cylinder and the torus.

[BibT_eX]

[DOI]

Eur. J. Comb., 2021

Bounding the number of cycles in a graph in terms of its degree sequence.

[BibT_eX]

[DOI]

Eur. J. Comb., 2021

Cyclic coloring of plane graphs with maximum face size 16 and 17.

[BibT_eX]

[DOI]

Eur. J. Comb., 2021

A Thomassen-type method for planar graph recoloring.

[BibT_eX]

[DOI]

Carl Feghali

Eur. J. Comb., 2021

A note on sublinear separators and expansion.

[BibT_eX]

[DOI]

Eur. J. Comb., 2021

Approximation metatheorem for fractionally treewidth-fragile graphs.

[BibT_eX]

[DOI]

CoRR, 2021

Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs.

[BibT_eX]

[DOI]

Abhiruk Lahiri

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

(3a: a)-List-Colorability of Embedded Graphs of Girth at Least Five.

[BibT_eX]

[DOI]

Xiaolan Hu

SIAM J. Discret. Math., 2020

Fractional Coloring of Planar Graphs of Girth Five.

[BibT_eX]

[DOI]

Xiaolan Hu

SIAM J. Discret. Math., 2020

Flexibility of planar graphs of girth at least six.

[BibT_eX]

[DOI]

J. Graph Theory, 2020

Three-coloring triangle-free graphs on surfaces III. Graphs of girth five.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2020

Notes on Graph Product Structure Theory.

[BibT_eX]

[DOI]

CoRR, 2020

On Fractional Fragility Rates of Graph Classes.

[BibT_eX]

[DOI]

Electron. J. Comb., 2020

An Update on Reconfiguring $10$-Colorings of Planar Graphs.

[BibT_eX]

[DOI]

Carl Feghali

Electron. J. Comb., 2020

1-Subdivisions, the Fractional Chromatic Number and the Hall Ratio.

[BibT_eX]

[DOI]

Patrice Ossona de Mendez

Hehui Wu

Comb., 2020

Baker game and polynomial-time approximation schemes.

[BibT_eX]

[DOI]

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

2019

List coloring with requests.

[BibT_eX]

[DOI]

J. Graph Theory, 2019

Triangle-free planar graphs with the smallest independence number.

[BibT_eX]

[DOI]

J. Graph Theory, 2019

On distance r?dominating and 2r?independent sets in sparse graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2019

Treewidth of graphs with balanced separations.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2019

Triangle-free planar graphs with small independence number.

[BibT_eX]

[DOI]

Jordan Venters

Eur. J. Comb., 2019

Planar graphs without cycles of length 4 or 5 are (11: 3)-colorable.

[BibT_eX]

[DOI]

Xiaolan Hu

Eur. J. Comb., 2019

Bounded maximum degree conjecture holds precisely for c-crossing-critical graphs with c≤12.

[BibT_eX]

[DOI]

CoRR, 2019

On Generalized Choice and Coloring Numbers.

[BibT_eX]

[DOI]

Electron. J. Comb., 2019

Exponentially Many Nowhere-Zero ℤ3-, ℤ4-, and ℤ6-Flows.

[BibT_eX]

[DOI]

Robert Sámal

Comb., 2019

Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c <= 12.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Computational Geometry, 2019

2018

Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2018

Fine Structure of 4-Critical Triangle-Free Graphs III. General Surfaces.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2018

Complete graph immersions and minimum degree.

[BibT_eX]

[DOI]

Liana Yepremyan

J. Graph Theory, 2018

Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2018

Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2018

Planar graphs have two-coloring number at most 8.

[BibT_eX]

[DOI]

Adam Kabela

Tomás Kaiser

J. Comb. Theory B, 2018

On classes of graphs with strongly sublinear separators.

[BibT_eX]

[DOI]

Eur. J. Comb., 2018

Induced subdivisions and bounded expansion.

[BibT_eX]

[DOI]

Eur. J. Comb., 2018

Least conflict choosability.

[BibT_eX]

[DOI]

CoRR, 2018

Induced 2-Degenerate Subgraphs of Triangle-Free Planar Graphs.

[BibT_eX]

[DOI]

Tom Kelly

Electron. J. Comb., 2018

Treewidth of Grid Subsets.

[BibT_eX]

[DOI]

Eli Berger

Comb., 2018

Thin graph classes and polynomial-time approximation schemes.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Additive Non-Approximability of Chromatic Number in Proper Minor-Closed Classes.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Structure and Generation of Crossing-Critical Graphs.

[BibT_eX]

[DOI]

Petr Hlinený

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

2017

Fine Structure of 4-Critical Triangle-Free Graphs II. Planar Triangle-Free Graphs with Two Precolored 4-Cycles.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

5-list-coloring planar graphs with distant precolored vertices.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2017

5-choosability of graphs with crossings far apart.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2017

Irreducible 4-critical triangle-free toroidal graphs.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2017

Exponentially many nowhere-zero ℝ3-, ℝ4-, and ℝ6-flows.

[BibT_eX]

[DOI]

Robert Sámal

Electron. Notes Discret. Math., 2017

Triangle-free graphs of tree-width t are ⌈ (t+3)/2 ⌉-colorable.

[BibT_eX]

[DOI]

Eur. J. Comb., 2017

Do Triangle-Free Planar Graphs have Exponentially Many $3$-Colorings?

[BibT_eX]

[DOI]

Electron. J. Comb., 2017

Density of 5/2-critical graphs.

[BibT_eX]

[DOI]

Comb., 2017

Independent Sets near the Lower Bound in Bounded Degree Graphs.

[BibT_eX]

[DOI]

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Graphic TSP in Cubic Graphs.

[BibT_eX]

[DOI]

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

2016

Strongly Sublinear Separators and Polynomial Expansion.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2016

A Structure Theorem for Strong Immersions.

[BibT_eX]

[DOI]

Paul Wollan

J. Graph Theory, 2016

Crossing Numbers of Periodic Graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2016

Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2016

Packing six T-joins in plane graphs.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2016

Immersion in four-edge-connected graphs.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2016

Sublinear separators, fragility and subexponential expansion.

[BibT_eX]

[DOI]

Eur. J. Comb., 2016

2015

3-Coloring Triangle-Free Planar Graphs with a Precolored 8-Cycle.

[BibT_eX]

[DOI]

J. Graph Theory, 2015

Fractional Coloring of Triangle-Free Planar Graphs.

[BibT_eX]

[DOI]

Jan Volec

Electron. J. Comb., 2015

On Planar Boolean CSP.

[BibT_eX]

[DOI]

Martin Kupec

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

4-Critical Graphs on Surfaces Without Contractible $(\le\!4)$-Cycles.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2014

Strong Immersions and Maximum Degree.

[BibT_eX]

[DOI]

Tereza Klimosová

SIAM J. Discret. Math., 2014

Subcubic triangle-free graphs have fractional chromatic number at most 14/5.

[BibT_eX]

[DOI]

Jan Volec

J. Lond. Math. Soc., 2014

3-choosability of planar graphs with ( 4)-cycles far apart.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2014

Distance-two coloring of sparse graphs.

[BibT_eX]

[DOI]

Louis Esperet

Eur. J. Comb., 2014

Planar 4-critical graphs with four triangles.

[BibT_eX]

[DOI]

Oleg V. Borodin

Alexandr V. Kostochka

Matthew P. Yancey

Eur. J. Comb., 2014

List-coloring apex-minor-free graphs.

[BibT_eX]

[DOI]

CoRR, 2014

A minimum degree condition forcing complete graph immersion.

[BibT_eX]

[DOI]

Comb., 2014

Large Independent Sets in Triangle-Free Planar Graphs.

[BibT_eX]

[DOI]

Matthias Mnich

Proceedings of the Algorithms - ESA 2014, 2014

A Dynamic Data Structure for MSO Properties in Graphs with Bounded Tree-Depth.

[BibT_eX]

[DOI]

Martin Kupec

Vojtech Tuma

Proceedings of the Algorithms - ESA 2014, 2014

2013

Star Chromatic Index.

[BibT_eX]

[DOI]

Robert Sámal

J. Graph Theory, 2013

Sub-exponentially many 3-colorings of triangle-free planar graphs.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2013

Testing first-order properties for subclasses of sparse graphs.

[BibT_eX]

[DOI]

J. ACM, 2013

Constant-factor approximation of the domination number in sparse graphs.

[BibT_eX]

[DOI]

Eur. J. Comb., 2013

4-critical graphs on surfaces without contractible (<=4)-cycles

[BibT_eX]

[DOI]

CoRR, 2013

Dynamic Data Structure for Tree-Depth Decomposition.

[BibT_eX]

[DOI]

Martin Kupec

Vojtech Tuma

CoRR, 2013

Chromatic number and complete graph substructures for degree sequences.

[BibT_eX]

[DOI]

Comb., 2013

A Dynamic Data Structure for Counting Subgraphs in Sparse Graphs.

[BibT_eX]

[DOI]

Vojtech Tuma

Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

List-coloring embedded graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Spectrally degenerate graphs: Hereditary case.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2012

Bipartizing fullerenes.

[BibT_eX]

[DOI]

Eur. J. Comb., 2012

Classes of graphs with small rank decompositions are X-bounded.

[BibT_eX]

[DOI]

Eur. J. Comb., 2012

Forbidden graphs for tree-depth.

[BibT_eX]

[DOI]

Archontia C. Giannopoulou

Dimitrios M. Thilikos

Eur. J. Comb., 2012

A stronger structure theorem for excluded topological minors

[BibT_eX]

[DOI]

CoRR, 2012

2011

Graphs with Two Crossings Are 5-Choosable.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2011

Randić index and the diameter of a graph.

[BibT_eX]

[DOI]

Eur. J. Comb., 2011

2010

3-Choosability of Triangle-Free Planar Graphs with Constraints on 4-Cycles.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2010

Non-rainbow colorings of 3-, 4- and 5-connected plane graphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2010

On recognizing graphs by numbers of homomorphisms.

[BibT_eX]

[DOI]

J. Graph Theory, 2010

Small graph classes and bounded expansion.

[BibT_eX]

[DOI]

Serguei Norine

J. Comb. Theory B, 2010

Spectral radius of finite and infinite planar graphs and of graphs of bounded genus.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2010

Crossing-critical graphs with large maximum degree.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2010

A note on antisymmetric flows in graphs.

[BibT_eX]

[DOI]

Tomás Kaiser

Eur. J. Comb., 2010

Toughness threshold for the existence of 2-walks in K4-minor-free graphs.

[BibT_eX]

[DOI]

Jakub Teska

Discret. Math., 2010

Pattern Hypergraphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2010

On a Rado Type Problem for Homogeneous Second Order Linear Recurrences.

[BibT_eX]

[DOI]

Electron. J. Comb., 2010

Deciding First-Order Properties for Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

k-Chromatic Number of Graphs on Surfaces.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2009

Matchings and Nonrainbow Colorings.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2009

Spectral radius of finite and infinite planar graphs and of graphs of bounded genus (extended abstract).

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2009

Planar graphs without 3-, 7-, and 8-cycles are 3-choosable.

[BibT_eX]

[DOI]

Discret. Math., 2009

Two-factors in orientated graphs with forbidden transitions.

[BibT_eX]

[DOI]

Discret. Math., 2009

Distance constrained labelings of planar graphs with no short cycles.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

Algorithms for Classes of Graphs with Bounded Expansion.

[BibT_eX]

[DOI]

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

Three-coloring triangle-free planar graphs in linear time.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Coloring triangle-free graphs on surfaces.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Planar Graphs of Odd-Girth at Least 9 are Homomorphic to the Petersen Graph.

[BibT_eX]

[DOI]

Tomás Valla

SIAM J. Discret. Math., 2008

List-Coloring Squares of Sparse Subcubic Graphs.

[BibT_eX]

[DOI]

Martin Tancer

SIAM J. Discret. Math., 2008

Coloring squares of planar graphs with girth six.

[BibT_eX]

[DOI]

Eur. J. Comb., 2008

On forbidden subdivision characterizations of graph classes.

[BibT_eX]

[DOI]

Eur. J. Comb., 2008

2007

Probabilistic strategies for the partition and plurality problems.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2007

Four gravity results.

[BibT_eX]

[DOI]

Tomás Valla

Discret. Math., 2007

2006

A Theorem About a Contractible and Light Edge.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2006

Eulerian colorings and the bipartizing matchings conjecture of Fleischner.

[BibT_eX]

[DOI]

Tomás Kaiser

Eur. J. Comb., 2006

2005

Coloring face hypergraphs on surfaces.

[BibT_eX]

[DOI]

Eur. J. Comb., 2005

Three Optimal Algorithms for Balls of Three Colors.

[BibT_eX]

[DOI]

Proceedings of the STACS 2005, 2005

On the Complexity of the G-Reconstruction Problem.

[BibT_eX]

[DOI]

Vít Jelínek

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

2004

Locally consistent constraint satisfaction problems

[BibT_eX]

[DOI]

Ondrej Pangrác

Electron. Colloquium Comput. Complex., 2004

An Algorithm for Cyclic Edge Connectivity of Cubic Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2004

Locally Consistent Constraint Satisfaction Problems: (Extended Abstract).

[BibT_eX]

[DOI]

Ondrej Pangrác

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

Noncrossing Hamiltonian Paths in Geometric Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, 11th International Symposium, 2003

2002

Complexity of Pattern Coloring of Cycle Systems.

[BibT_eX]

[DOI]

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

2001

On Planar Mixed Hypergraphs.

[BibT_eX]

[DOI]