8 papers
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…
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…
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…
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 the 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…