We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with $c\ge 13$ and $d\ge 1$, we give first explicit constructions of $c$-crossing-critical graphs containing a vertex of degree greater than $d$. We also show that such unbounded degree constructions do not exist for $c\le 12$. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvořák and Mohar, holds true, surprisingly, exactly for the values $c\le 12$.
COBISS.SI-ID: 18858585
We give a new proof of the fact that every planar graph is 5-choosable, and use it to show that every graph drawn in the plane so that the distance between every pair of crossings is at least 15 is 5-choosable. At the same time we may allow some vertices to have lists of size four only, as long as they are far apart and far from the crossings.
COBISS.SI-ID: 18214489
The results of this paper provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. The running time of the algorithm is quadratic. Moreover, we extend the algorithm to output an embedding (rotation system), whose genus is arbitrarily close to the minimum genus. This second algorithm is an Efficient Polynomial-time Randomized Approximation Scheme (EPRAS) and the expected running time is also quadratic.
COBISS.SI-ID: 18855001
We consider the problem of finding a 1-planar drawing for a general graph, where a 1-planar drawing is a drawing in which each edge participates in at most one crossing. Since this problem is known to be NP-hard we investigate the parameterized complexity of the problem with respect to the vertex cover number, tree-depth, and cyclomatic number. For these parameters we construct fixed-parameter tractable algorithms. However, the problem remains NP-complete for graphs of bounded bandwidth, pathwidth, or treewidth.
COBISS.SI-ID: 18208345
We introduce two new partial orders on the standard Young tableaux of a given partition shape, in analogy with the strong and weak Bruhat orders on permutations. Both posets are ranked by the major index statistic offset by a fixed shift. The existence of such ranked poset structures allows us to classify the realizable major index statistics on standard tableaux of arbitrary straight shape and certain skew shapes. By a theorem of Lusztig-Stanley [R. P. Stanley, Bull. Am. Math. Soc., New Ser. 1, 475-511 (1979) Prop. 4.11], this classification can be interpreted as determining which irreducible representations of the symmetric group exist in which homogeneous components of the corresponding coinvariant algebra, strengthening a recent result of the third author for the modular major index. Our approach is to identify patterns in standard tableaux that allow one to mutate descent sets in a controlled manner. By work of G. Lusztig [Invent. Math. 43, 125--175 (1977] and J. R. Stembridge [Pac. J. Math. 140, No. 2, 353--396 (1989)], the arguments extend to a classification of all nonzero fake degrees of coinvariant algebras for finite complex reflection groups in the infinite family of Shephard-Todd groups.
COBISS.SI-ID: 24348675