17 citations · 36 across the 19 of their papers we have counts for
23 papers
Excluding paths and bicliques
Maria Chudnovsky, Julien Codsi, Matjaž Krnc +1
Classes of graphs excluding a path and a biclique as induced subgraphs are extensively studied in the literature. One of the key structural results for such graphs is a Ramsey-type…
Dominated balanced separators in wheel-induced-minor-free graphs
Maria Chudnovsky, J. Pascal Gollin, Matjaž Krnc +1
Gartland and Lokshtanov conjectured that every graph that excludes some planar graph as an induced minor has a balanced separator, that is, a separator whose deletion leaves every…
Row Impartial Terminus
Eric Gottlieb, Dawood Khatana, Matjaž Krnc +2
We introduce Row Impartial Terminus (RIT), an impartial combinatorial game played on integer partitions. We show that any position in RIT can be uniquely decomposed into a core and…
Sandwich Monotonicity and Recognition of Weighted Graph Classes
Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler +5
Edge-weighted graphs play an important role in the theory of Robinsonian matrices and similarity theory, particularly via the concept of level graphs, that is, graphs obtained from…
Linear colorings of graphs
Claire Hilaire, Matjaž Krnc, Martin Milanič +1
Motivated by algorithmic applications, Kun, O'Brien, Pilipczuk, and Sullivan introduced the parameter linear chromatic number as a relaxation of treedepth and proved that the two p…
Young domination on Hamming rectangles
Janko Gravner, Matjaž Krnc, Martin Milanič +1
We introduce a family of domination-type problems in Cartesian products of two graphs. The framework captures several well-studied topics, including variants of bootstrap percolati…
Ramsey multiplicity of apices of trees
Daniel Kráľ, Matjaž Krnc, Ander Lamaison
A graph is common if its Ramsey multiplicity, i.e., the minimum number of monochromatic copies of contained in any -edge-coloring of , is asymptotically the same as…
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…
Growing Trees and Amoebas' Replications
Vladimir Gurvich, Matjaž Krnc, Mikhail Vyalyi
An amoeba is a tree together with instructions how to iteratively grow trees by adding paths of a fixed length . This paper analyses such a growth process. An amoeba is morta…
Fair Allocation Algorithms for Indivisible Items under Structured Conflict Constraints
Nina Chiarelli, Matjaž Krnc, Martin Milanič +2
We consider the fair allocation of indivisible items to several agents with additional conflict constraints. These are represented by a conflict graph where each item corresponds t…
Avoidability beyond paths
Vladimir Gurvich, Matjaž Krnc, Martin Milanič +1
The concept of avoidable paths in graphs was introduced by Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius in 2019 as a common generalization of avoidable vertices and simpli…
Some results on LCTR, an impartial game on partitions
Eric Gottlieb, Jelena Ilić, Matjaž Krnc
We apply the Sprague-Grundy Theorem to LCTR, a new impartial game on partitions in which players take turns removing either the Left Column or the Top Row of the corresponding Youn…
Sprague-Grundy values and complexity for LCTR
Eric Gottlieb, Matjaž Krnc, Peter Muršič
Given an integer partition of , we consider the impartial combinatorial game LCTR in which moves consist of removing either the left column or top row of its Young diagram. We s…
Graphs where Search Methods are Indistinguishable
Matjaž Krnc, Nevena Pivač
Graph searching is one of the simplest and most widely used tools in graph algorithms. Every graph search method is defined using some particular selection rule, and the analysis o…
Graphs with at most two moplexes
Clément Dallard, Robert Ganian, Meike Hatzel +2
A moplex is a natural graph structure that arises when lifting Dirac's classical theorem from chordal graphs to general graphs. While every non-complete graph has at least two mopl…
Shifting paths to avoidable ones
Vladimir Gurvich, Matjaž Krnc, Martin Milanič +1
An extension of an induced path in a graph is an induced path such that deleting the endpoints of results in . An induced path in a graph is said to be avoidab…
Fair allocation of indivisible items with conflict graphs
Nina Chiarelli, Matjaž Krnc, Martin Milanič +3
We consider the fair allocation of indivisible items to several agents and add a graph theoretical perspective to this classical problem. Namely, we introduce an incompatibility re…
Recognizing Graph Search Trees
Jesse Beisegel, Carolin Denkert, Ekkehard Köhler +4
Graph searches and the corresponding search trees can exhibit important structural properties and are used in various graph algorithms. The problem of deciding whether a given span…
On the End-Vertex Problem of Graph Searches
Jesse Beisegel, Carolin Denkert, Ekkehard Köhler +4
End vertices of graph searches can exhibit strong structural properties and are crucial for many graph algorithms. The problem of deciding whether a given vertex of a graph is an e…
Positive Aging Admits Fast Asynchronous Plurality Consensus
Gregor Bankhamer, Robert Elsässer, Dominik Kaaser +1
We study distributed plurality consensus among nodes, each of which initially holds one of opinions. The goal is to eventually agree on the initially dominant opinion. We c…
Recognizing generalized Petersen graphs in linear time
Matjaž Krnc, Robin J. Wilson
By identifying a local property which structurally classifies any edge, we show that the family of generalized Petersen graphs can be recognized in linear time.
Closeness Centralization Measure for Two-mode Data of Prescribed Sizes
Matjaž Krnc, Jean-Sébastien Sereni, Riste Škrekovski +1
We confirm a conjecture by Everett, Sinclair, and Dankelmann~[Some Centrality results new and old, J. Math. Sociology 28 (2004), 215--227] regarding the problem of maximizing close…
Cyclic colorings of plane graphs with independent faces
Jernej Azarija, Daniel Král', Rok Erman +2
Let G be a plane graph with maximum face size D. If all faces of G with size four or more are vertex disjoint, then G has a cyclic coloring with D+1 colors, i.e., a coloring such t…