Charles University

output

19922026

most citedObservation of a new particle in the search for the Standard Model Higgs boson with the ATLAS detector at the LHC

10.9k citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions

Showing 2019 · math.COShow all

21 papers · 2 filters

math.CO2019

Two examples of Wilf-collapse

Michael Albert, Vít Jelínek, Michal Opler

Two permutation classes, the X-class and subpermutations of the increasing oscillation are shown to exhibit an exponential Wilf-collapse. This means that the number of distinct enu…

math.CO2019

A relaxed version of Šoltés's problem and cactus graphs

Jan Bok, Nikola Jedličková, Jana Maxová

The \emph{Wiener index} is one of the most widely studied parameters in chemical graph theory. It is defined as the sum of the lengths of the shortest paths between all unordered p…

math.CO2019★ 1 cited

Minimal Representations of Order Types by Geometric Graphs

Oswin Aichholzer, Martin Balko, Michael Hoffmann +8

In order to have a compact visualization of the order type of a given point set S, we are interested in geometric graphs on S with few edges that unambiguously display the order ty…

math.CO2019★ 1 cited

Bounding Radon numbers via Betti numbers

Zuzana Patáková

We prove general topological Radon-type theorems for sets in $R^{d}$ or on a surface. Combined with a recent result of Holmsen and Lee, we also obtain fractional Helly theore…

math.CO2019★ 3 cited

Independence number in triangle-free graphs avoiding a minor

Zdeněk Dvořák, Liana Yepremyan

The celebrated Hadwiger's conjecture states that if a graph contains no $K_{t + 1}$ minor then it is $t$ -colourable. If true, it would in particular imply that every $n$ -vertex $K_{t…

math.CO2019

Even maps, the Colin de~Verdière number and representations of graphs

Vojtěch Kaluža, Martin Tancer

Van der Holst and Pendavingh introduced a graph parameter $σ$ , which coincides with the more famous Colin de Verdière graph parameter $μ$ for small values. However, the definition…

math.CO2019

Coloring count cones of planar graphs

Zdeněk Dvořák, Bernard Lidický

For a plane near-triangulation $G$ with the outer face bounded by a cycle $C$ , let $n_{G}^{⋆}$ denote the function that to each $4$ -coloring $ψ$ of $C$ assigns the number of ways $…

math.CO2019

A Method to construct all the Paving Matroids over a Finite Set

B. Mederos, I. Pérez-Cabrera, M. Takane +2

We give a characterization of a matroid to be paving, through its set of hyperplanes and give an algorithm to construct all of them.

math.CO2019★ 3 cited

Big Ramsey degrees of 3-uniform hypergraphs

Martin Balko, David Chodounský, Jan Hubička +2

Given a countably infinite hypergraph $R$ and a finite hypergraph $A$ , the big Ramsey degree of $A$ in $R$ is the least number $L$ such that, fo…

math.CO2019★ 8 cited

Edge-ordered Ramsey numbers

Martin Balko, Máté Vizer

We introduce and study a variant of Ramsey numbers for edge-ordered graphs, that is, graphs with linearly ordered sets of edges. The edge-ordered Ramsey number $\overline{R}_e(\mat…

math.CO2019★ 4 cited

Ramsey numbers and monotone colorings

Martin Balko

For positive integers $N$ and $r \geq 2$ , an $r$ -monotone coloring of $(r { 1 , \dots , N })$ is a 2-coloring by $- 1$ and $+ 1$ that is monotone on the lexicographically ordered…

math.CO2019

A Turán-type theorem for large-distance graphs in Euclidean spaces, and related isodiametric problems

Martin Doležal, Jan Hladký, Jan Kolář +3

Given a measurable set $A \subset R^{d}$ we consider the "large-distance graph" $G_{A}$ , on the ground set $A$ , in which each pair of points from $A$ whose distance is…

math.CO2019★ 1 cited

Extending partial automorphisms of $n$ -partite tournaments

Jan Hubička, Colin Jahel, Matěj Konečný +1

We prove that for every $n \geq 2$ the class of all finite $n$ -partite tournaments (orientations of complete $n$ -partite graphs) has the extension property for partial automorphisms…

math.CO2019★ 3 cited

Flexibility of planar graphs without 4-cycles

Tomáš Masařík

Proper graph coloring assigns different colors to adjacent vertices of the graph. Usually, the number of colors is fixed or as small as possible. Consider applications (e.g. varian…

math.CO2019★ 7 cited

Tutte's dichromate for signed graphs

Andrew Goodall, Bart Litjens, Guus Regts +1

We introduce the ``trivariate Tutte polynomial" of a signed graph as an invariant of signed graphs up to vertex switching that contains among its evaluations the number of proper c…

math.CO2019★ 7 cited

Flexibility of planar graphs of girth at least six

Zdeněk Dvořák, Tomáš Masařík, Jan Musílek +1

Let G be a planar graph with a list assignment L. Suppose a preferred color is given for some of the vertices. We prove that if G has girth at least six and all lists have size at…

math.CO2019★ 8 cited

Flexibility of triangle-free planar graphs

Zdeněk Dvořák, Tomáš Masařík, Jan Musílek +1

Let G be a planar graph with a list assignment L. Suppose a preferred color is given for some of the vertices. We prove that if G is triangle-free and all lists have size at least…

math.CO2019★ 4 cited

Maximum Wiener index of unicyclic graphs with given bipartition

Jan Bok, Nikola Jedličková, Jana Maxová

The \emph{Wiener index} is a widely studied topological index of graphs. One of the main problems in the area is to determine which graphs of given properties attain the extremal v…

math.CO2019★ 4 cited

The independence number of HH-homogeneous graphs and a classification of MB-homogeneous graphs

Andrés Aranda, David Hartman

We show that the independence number of a countably infinite HH-homogeneous graph that does not contain the Rado graph as a spanning subgraph is finite and present a classification…

math.CO2019★ 7 cited

On Extremal Graphs of Weighted Szeged Index

Jan Bok, Boris Furtula, Nikola Jedličková +1

An extension of the well-known Szeged index was introduced recently, named as weighted Szeged index ( $sz (G)$ ). This paper is devoted to characterizing the extremal trees a…

math.CO2019★ 9 cited

Extending partial isometries of antipodal graphs

Matěj Konečný

We prove EPPA (extension property for partial automorphisms) for all antipodal classes from Cherlin's list of metrically homogeneous graphs, thereby answering a question of Aranda…

Two examples of Wilf-collapse

A relaxed version of Šoltés's problem and cactus graphs

Minimal Representations of Order Types by Geometric Graphs

Bounding Radon numbers via Betti numbers

Independence number in triangle-free graphs avoiding a minor

Even maps, the Colin de~Verdière number and representations of graphs

Coloring count cones of planar graphs

A Method to construct all the Paving Matroids over a Finite Set

Big Ramsey degrees of 3-uniform hypergraphs

Edge-ordered Ramsey numbers

Ramsey numbers and monotone colorings

A Turán-type theorem for large-distance graphs in Euclidean spaces, and related isodiametric problems

Extending partial automorphisms of n-partite tournaments

Flexibility of planar graphs without 4-cycles

Tutte's dichromate for signed graphs

Flexibility of planar graphs of girth at least six

Flexibility of triangle-free planar graphs

Maximum Wiener index of unicyclic graphs with given bipartition

The independence number of HH-homogeneous graphs and a classification of MB-homogeneous graphs

On Extremal Graphs of Weighted Szeged Index

Extending partial isometries of antipodal graphs

Extending partial automorphisms of $n$ -partite tournaments