11 citations · 27 across the 12 of their papers we have counts for
14 papers
Awesome graph parameters
Kenny Bešter Štorgel, Clément Dallard, Vadim Lozin +2
For a graph , we denote by the size of a maximum independent set and by the size of a maximum clique in . Our paper lies on the edge of two lines of research, r…
On -Roman graphs: complexity of recognition and the case of split graphs
Kenny Bešter Štorgel, Nina Chiarelli, Lara Fernández +4
For a positive integer , a -Roman dominating function of a graph is a function satisfying $\sum_{u\in N(v)} f(u) \geq…
Tree decompositions meet induced matchings: beyond Max Weight Independent Set
Paloma T. Lima, Martin Milanič, Peter Muršič +3
For a tree decomposition of a graph , by we denote the size of a largest induced matching in all of whose edges intersect one bag of $\mathcal…
Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
Clément Dallard, Matjaž Krnc, O-joung Kwon +4
Many recent works address the question of characterizing induced obstructions to bounded treewidth. In 2022, Lozin and Razgon completely answered this question for graph classes de…
Packing coloring of hypercubes with extended Hamming codes
Petr Gregor, Jaka Kranjc, Borut Lužar +1
A {\em packing coloring} of a graph is a mapping assigning a positive integer (a color) to every vertex of such that every two vertices of color are at distance at leas…
Twin-width of graphs on surfaces
Daniel Kráľ, Kristýna Pekárková, Kenny Štorgel
Twin-width is a width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS'20, JACM'22], which has many structural and algorithmic applications. We prove that the twin…
Functionality of box intersection graphs
Clément Dallard, Vadim Lozin, Martin Milanič +2
Functionality is a graph complexity measure that extends a variety of parameters, such as vertex degree, degeneracy, clique-width, or twin-width. In the present paper, we show that…
Locally irregular edge-coloring of subcubic graphs
Borut Lužar, Mária Maceková, Simona Rindošová +3
A graph is {\em locally irregular} if no two adjacent vertices have the same degree. A {\em locally irregular edge-coloring} of a graph is such an (improper) edge-coloring that…
Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
Clément Dallard, Martin Milanič, Kenny Štorgel
We continue the study of -bounded graph classes, that is, hereditary graph classes in which the treewidth can only be large due to the presence of a large clique,…
-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4
Hoang La, Kenny Štorgel
In the past various distance based colorings on planar graphs were introduced. We turn our focus to three of them, namely -distance coloring, injective coloring, and exact squar…
Treewidth versus clique number. II. Tree-independence number
Clément Dallard, Martin Milanič, Kenny Štorgel
In 2020, we initiated a systematic study of graph classes in which the treewidth can only be large due to the presence of a large clique, which we call -bounded. W…
Further Extensions of the Grötzsch Theorem
Hoang La, Borut Lužar, Kenny Štorgel
The Grötzsch Theorem states that every triangle-free planar graph admits a proper -coloring. Among many of its generalizations, the one of Grünbaum and Aksenov, giving -color…
3-facial edge-coloring of plane graphs
Mirko Horňák, Borut Lužar, Kenny Štorgel
An -facial edge-coloring of a plane graph is a coloring of its edges such that any two edges at distance at most on a boundary walk of any face receive distinct colors…
Treewidth versus clique number. I. Graph classes with a forbidden structure
Clément Dallard, Martin Milanič, Kenny Štorgel
Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of…