2024
Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations.
J. Comb. Theory, Ser. B, January, 2024
A Strengthening and an Efficient Implementation of Alon-Tarsi List Coloring Method.
Electron. J. Comb., 2024
2023
Induced odd cycle packing number, independent sets, and chromatic number.
J. Graph Theory, July, 2023
On Density of \(\boldsymbol{\mathbb{Z}_3}\) -Flow-Critical Graphs.
SIAM J. Discret. Math., June, 2023
Additive non-approximability of chromatic number in proper minor-closed classes.
J. Comb. Theory, Ser. B, 2023
A note on local search for hitting sets.
CoRR, 2023
Embedded graph 3-coloring and flows.
CoRR, 2023
An efficient implementation and a strengthening of Alon-Tarsi list coloring method.
CoRR, 2023
Maximum Edge Colouring Problem On Graphs That Exclude a Fixed Minor.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2023
Representation of Short Distances in Structurally Sparse Graphs.
Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023
2022
On Decidability of Hyperbolicity.
Comb., December, 2022
Coloring count cones of planar graphs.
J. Graph Theory, 2022
On weighted sublinear separators.
J. Graph Theory, 2022
Triangle-free planar graphs with at most 64n0.731 3-colorings.
J. Comb. Theory, Ser. B, 2022
Characterization of 4-critical triangle-free toroidal graphs.
J. Comb. Theory, Ser. B, 2022
Three-coloring triangle-free graphs on surfaces VII. A linear-time algorithm.
J. Comb. Theory, Ser. B, 2022
Square roots of nearly planar graphs.
CoRR, 2022
Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c ≤ 12.
Comb., 2022
Approximation Metatheorems for Classes with Bounded Expansion.
Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022
Weak Coloring Numbers of Intersection Graphs.
Proceedings of the 38th International Symposium on Computational Geometry, 2022
On Comparable Box Dimension.
Proceedings of the 38th International Symposium on Computational Geometry, 2022
2021
Sublinear Separators in Intersection Graphs of Convex Shapes.
SIAM J. Discret. Math., 2021
Flexibility of triangle-free planar graphs.
J. Graph Theory, 2021
Single-conflict colouring.
J. Graph Theory, 2021
Three-coloring triangle-free graphs on surfaces IV. Bounding face sizes of 4-critical graphs.
J. Comb. Theory, Ser. B, 2021
Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies.
J. Comb. Theory, Ser. B, 2021
Coloring near-quadrangulations of the cylinder and the torus.
Eur. J. Comb., 2021
Bounding the number of cycles in a graph in terms of its degree sequence.
Eur. J. Comb., 2021
Cyclic coloring of plane graphs with maximum face size 16 and 17.
Eur. J. Comb., 2021
A Thomassen-type method for planar graph recoloring.
Eur. J. Comb., 2021
A note on sublinear separators and expansion.
Eur. J. Comb., 2021
Approximation metatheorem for fractionally treewidth-fragile graphs.
CoRR, 2021
Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs.
Proceedings of the 29th Annual European Symposium on Algorithms, 2021
2020
(3a: a)-List-Colorability of Embedded Graphs of Girth at Least Five.
SIAM J. Discret. Math., 2020
Fractional Coloring of Planar Graphs of Girth Five.
SIAM J. Discret. Math., 2020
Flexibility of planar graphs of girth at least six.
J. Graph Theory, 2020
Three-coloring triangle-free graphs on surfaces III. Graphs of girth five.
J. Comb. Theory, Ser. B, 2020
Notes on Graph Product Structure Theory.
CoRR, 2020
On Fractional Fragility Rates of Graph Classes.
Electron. J. Comb., 2020
An Update on Reconfiguring $10$-Colorings of Planar Graphs.
Electron. J. Comb., 2020
1-Subdivisions, the Fractional Chromatic Number and the Hall Ratio.
Comb., 2020
Baker game and polynomial-time approximation schemes.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020
2019
List coloring with requests.
J. Graph Theory, 2019
Triangle-free planar graphs with the smallest independence number.
J. Graph Theory, 2019
On distance r?dominating and 2r?independent sets in sparse graphs.
J. Graph Theory, 2019
Treewidth of graphs with balanced separations.
J. Comb. Theory, Ser. B, 2019
Triangle-free planar graphs with small independence number.
Eur. J. Comb., 2019
Planar graphs without cycles of length 4 or 5 are (11: 3)-colorable.
Eur. J. Comb., 2019
Bounded maximum degree conjecture holds precisely for c-crossing-critical graphs with c≤12.
CoRR, 2019
On Generalized Choice and Coloring Numbers.
Electron. J. Comb., 2019
Exponentially Many Nowhere-Zero ℤ<sub>3</sub>-, ℤ<sub>4</sub>-, and ℤ<sub>6</sub>-Flows.
Comb., 2019
2018
Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains.
SIAM J. Discret. Math., 2018
Fine Structure of 4-Critical Triangle-Free Graphs III. General Surfaces.
SIAM J. Discret. Math., 2018
Complete graph immersions and minimum degree.
J. Graph Theory, 2018
Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8.
J. Comb. Theory, Ser. B, 2018
Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk.
J. Comb. Theory, Ser. B, 2018
Planar graphs have two-coloring number at most 8.
J. Comb. Theory, Ser. B, 2018
On classes of graphs with strongly sublinear separators.
Eur. J. Comb., 2018
Induced subdivisions and bounded expansion.
Eur. J. Comb., 2018
Least conflict choosability.
CoRR, 2018
Induced 2-Degenerate Subgraphs of Triangle-Free Planar Graphs.
Electron. J. Comb., 2018
Treewidth of Grid Subsets.
Comb., 2018
Thin graph classes and polynomial-time approximation schemes.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018
Structure and Generation of Crossing-Critical Graphs.
Proceedings of the 34th International Symposium on Computational Geometry, 2018
2017
Large Independent Sets in Triangle-Free Planar Graphs.
SIAM J. Discret. Math., 2017
Fine Structure of 4-Critical Triangle-Free Graphs II. Planar Triangle-Free Graphs with Two Precolored 4-Cycles.
SIAM J. Discret. Math., 2017
5-list-coloring planar graphs with distant precolored vertices.
J. Comb. Theory, Ser. B, 2017
5-choosability of graphs with crossings far apart.
J. Comb. Theory, Ser. B, 2017
Irreducible 4-critical triangle-free toroidal graphs.
Electron. Notes Discret. Math., 2017
Exponentially many nowhere-zero ℝ<sub>3</sub>-, ℝ<sub>4</sub>-, and ℝ<sub>6</sub>-flows.
Electron. Notes Discret. Math., 2017
Triangle-free graphs of tree-width t are ⌈ (t+3)/2 ⌉-colorable.
Eur. J. Comb., 2017
Do Triangle-Free Planar Graphs have Exponentially Many $3$-Colorings?
Electron. J. Comb., 2017
Density of 5/2-critical graphs.
Comb., 2017
Independent Sets near the Lower Bound in Bounded Degree Graphs.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017
Graphic TSP in Cubic Graphs.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017
2016
Strongly Sublinear Separators and Polynomial Expansion.
SIAM J. Discret. Math., 2016
A Structure Theorem for Strong Immersions.
J. Graph Theory, 2016
Crossing Numbers of Periodic Graphs.
J. Graph Theory, 2016
Three-coloring triangle-free graphs on surfaces I. Extending a coloring to a disk with one triangle.
J. Comb. Theory, Ser. B, 2016
Packing six T-joins in plane graphs.
J. Comb. Theory, Ser. B, 2016
Immersion in four-edge-connected graphs.
J. Comb. Theory, Ser. B, 2016
Sublinear separators, fragility and subexponential expansion.
Eur. J. Comb., 2016
2015
3-Coloring Triangle-Free Planar Graphs with a Precolored 8-Cycle.
J. Graph Theory, 2015
Fractional Coloring of Triangle-Free Planar Graphs.
Electron. J. Comb., 2015
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015
2014
4-Critical Graphs on Surfaces Without Contractible $(\le\!4)$-Cycles.
SIAM J. Discret. Math., 2014
Strong Immersions and Maximum Degree.
SIAM J. Discret. Math., 2014
Subcubic triangle-free graphs have fractional chromatic number at most 14/5.
J. Lond. Math. Soc., 2014
3-choosability of planar graphs with ( 4)-cycles far apart.
J. Comb. Theory, Ser. B, 2014
Distance-two coloring of sparse graphs.
Eur. J. Comb., 2014
Planar 4-critical graphs with four triangles.
Eur. J. Comb., 2014
List-coloring apex-minor-free graphs.
CoRR, 2014
A minimum degree condition forcing complete graph immersion.
Comb., 2014
A Dynamic Data Structure for MSO Properties in Graphs with Bounded Tree-Depth.
Proceedings of the Algorithms - ESA 2014, 2014
2013
Sub-exponentially many 3-colorings of triangle-free planar graphs.
J. Comb. Theory, Ser. B, 2013
Testing first-order properties for subclasses of sparse graphs.
J. ACM, 2013
Constant-factor approximation of the domination number in sparse graphs.
Eur. J. Comb., 2013
4-critical graphs on surfaces without contractible (<=4)-cycles
CoRR, 2013
Dynamic Data Structure for Tree-Depth Decomposition.
CoRR, 2013
Chromatic number and complete graph substructures for degree sequences.
Comb., 2013
A Dynamic Data Structure for Counting Subgraphs in Sparse Graphs.
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013
List-coloring embedded graphs.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013
2012
Spectrally degenerate graphs: Hereditary case.
J. Comb. Theory, Ser. B, 2012
Classes of graphs with small rank decompositions are X-bounded.
Eur. J. Comb., 2012
Forbidden graphs for tree-depth.
Eur. J. Comb., 2012
A stronger structure theorem for excluded topological minors
CoRR, 2012
2011
Three-coloring triangle-free planar graphs in linear time.
ACM Trans. Algorithms, 2011
Graphs with Two Crossings Are 5-Choosable.
SIAM J. Discret. Math., 2011
Randić index and the diameter of a graph.
Eur. J. Comb., 2011
2010
3-Choosability of Triangle-Free Planar Graphs with Constraints on 4-Cycles.
SIAM J. Discret. Math., 2010
Non-rainbow colorings of 3-, 4- and 5-connected plane graphs.
J. Graph Theory, 2010
On recognizing graphs by numbers of homomorphisms.
J. Graph Theory, 2010
Small graph classes and bounded expansion.
J. Comb. Theory, Ser. B, 2010
Spectral radius of finite and infinite planar graphs and of graphs of bounded genus.
J. Comb. Theory, Ser. B, 2010
Crossing-critical graphs with large maximum degree.
J. Comb. Theory, Ser. B, 2010
A note on antisymmetric flows in graphs.
Eur. J. Comb., 2010
Toughness threshold for the existence of 2-walks in K<sub>4</sub>-minor-free graphs.
Discret. Math., 2010
On a Rado Type Problem for Homogeneous Second Order Linear Recurrences.
Electron. J. Comb., 2010
Deciding First-Order Properties for Sparse Graphs.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010
2009
k-Chromatic Number of Graphs on Surfaces.
SIAM J. Discret. Math., 2009
Matchings and Nonrainbow Colorings.
SIAM J. Discret. Math., 2009
Spectral radius of finite and infinite planar graphs and of graphs of bounded genus (extended abstract).
Electron. Notes Discret. Math., 2009
Planar graphs without 3-, 7-, and 8-cycles are 3-choosable.
Discret. Math., 2009
Two-factors in orientated graphs with forbidden transitions.
Discret. Math., 2009
Distance constrained labelings of planar graphs with no short cycles.
Discret. Appl. Math., 2009
Algorithms for Classes of Graphs with Bounded Expansion.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2009
2008
Planar Graphs of Odd-Girth at Least 9 are Homomorphic to the Petersen Graph.
SIAM J. Discret. Math., 2008
List-Coloring Squares of Sparse Subcubic Graphs.
SIAM J. Discret. Math., 2008
Coloring squares of planar graphs with girth six.
Eur. J. Comb., 2008
On forbidden subdivision characterizations of graph classes.
Eur. J. Comb., 2008
2007
Probabilistic strategies for the partition and plurality problems.
Random Struct. Algorithms, 2007
Noncrossing Hamiltonian paths in geometric graphs.
Discret. Appl. Math., 2007
Coloring Triangle-Free Graphs on Surfaces.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007
2006
A Theorem About a Contractible and Light Edge.
SIAM J. Discret. Math., 2006
Eulerian colorings and the bipartizing matchings conjecture of Fleischner.
Eur. J. Comb., 2006
2005
Locally consistent constraint satisfaction problems.
Theor. Comput. Sci., 2005
Coloring face hypergraphs on surfaces.
Eur. J. Comb., 2005
Three Optimal Algorithms for Balls of Three Colors.
Proceedings of the STACS 2005, 2005
On the Complexity of the <i>G</i>-Reconstruction Problem.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005
2004
An Algorithm for Cyclic Edge Connectivity of Cubic Graphs.
Proceedings of the Algorithm Theory, 2004
Locally Consistent Constraint Satisfaction Problems: (Extended Abstract).
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004
2002
Complexity of Pattern Coloring of Cycle Systems.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002
2001
On Planar Mixed Hypergraphs.
Electron. J. Comb., 2001
