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 2013 · math.COShow all

22 papers · 2 filters

math.CO2013★ 30 cited

Crossing numbers and combinatorial characterization of monotone drawings of $K_{n}$

Martin Balko, Radoslav Fulek, Jan Kynčl

In 1958, Hill conjectured that the minimum number of crossings in a drawing of $K_{n}$ is exactly $Z(n) = \frac{1}{4} \lfloor\frac{n}{2}\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor…

math.CO2013★ 2 cited

The Potts model and chromatic functions of graphs

Martin Klazar, Martin Loebl, Iain Moffatt

The $U$ -polynomial of Noble and Welsh is known to have intimate connections with the Potts model as well as with several important graph polynomials. For each graph $G$ , $U (G)$ is…

math.CO2013★ 4 cited

On the Geometric Ramsey Number of Outerplanar Graphs

Josef Cibulka, Pu Gao, Marek Krčál +2

We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey num…

math.CO2013

Directed cycle double covers: structure and generation of hexagon graphs

Andrea Jiménez, Mihyun Kang, Martin Loebl

Jaeger's directed cycle double cover conjecture can be formulated as a problem of existence of special perfect matchings in a class of graphs that we call hexagon graphs. In this w…

math.CO2013★ 13 cited

Ramsey numbers of ordered graphs

Martin Balko, Josef Cibulka, Karel Král +1

An ordered graph is a pair $G = (G, ≺)$ where $G$ is a graph and $≺$ is a total ordering of its vertices. The ordered Ramsey number $R (G)$ is th…

math.CO2013★ 1 cited

On q-Series Identities Related to Interval Orders

George E. Andrews, Vít Jelínek

We prove several power series identities involving the refined generating function of interval orders, as well as the refined generating function of the self-dual interval orders.…

math.CO2013★ 10 cited

Saturated simple and $k$ -simple topological graphs

Jan Kynčl, János Pach, Radoš Radoičić +1

A simple topological graph $G$ is a graph drawn in the plane so that any pair of edges have at most one point in common, which is either an endpoint or a proper crossing. $G$ is ca…

math.CO2013★ 1 cited

Immersion in four-edge-connected graphs

Maria Chudnovsky, Zdeněk Dvořák, Tereza Klimošová +1

Fix g>1. Every graph of large enough tree-width contains a g x g grid as a minor; but here we prove that every four-edge-connected graph of large enough tree-width contains a g x g…

math.CO2013

Estimating the number of disjoint edges in simple topological graphs via cylindrical drawings

Radoslav Fulek

A topological graph drawn on a cylinder whose base is horizontal is \emph{angularly monotone} if every vertical line intersects every edge at most once. Let $c (n)$ denote the maxim…

math.CO2013★ 2 cited

Lower bounds on geometric Ramsey functions

Marek Eliáš, Jiří Matoušek, Edgardo Roldán-Pensado +1

We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in $R^{d}$ . A $k$ -ary semialgebraic predicate $Φ (x_{1}, \dots, x_{k})$ on $\mathbb{R…

math.CO2013★ 19 cited

Planar 4-critical graphs with four triangles

Oleg V. Borodin, Zdeněk Dvořák, Alexandr V. Kostochka +2

By the Grunbaum-Aksenov Theorem (extending Grotzsch's Theorem) every planar graph with at most three triangles is 3-colorable. However, there are infinitely many planar 4-critical…

math.CO2013★ 10 cited

3-coloring triangle-free planar graphs with a precolored 8-cycle

Zdeněk Dvořák, Bernard Lidický

Let G be a planar triangle-free graph and let C be a cycle in G of length at most 8. We characterize all situations where a 3-coloring of C does not extend to a proper 3-coloring o…

math.CO2013

Firefighting on square, hexagonal, and triangular grids

Tomas Gavenciak, Jan Kratochvil, Pawel Pralat

In this paper, we consider the \emph{firefighter problem} on a graph $G = (V, E)$ that is either finite or infinite. Suppose that a fire breaks out at a given vertex $v \in V$ . In eac…

math.CO2013★ 18 cited

A Model Theory Approach to Structural Limits

Jaroslav Nesetril, Patrice Ossona De Mendez

The goal of this paper is to unify two lines in a particular area of graph limits. First, we generalize and provide unified treatment of various graph limit concepts by means of a…

math.CO2013★ 23 cited

A unified approach to structural limits, and limits of graphs with bounded tree-depth

Jaroslav Nesetril, Patrice Ossona De Mendez

In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on a combination of model theory…

math.CO2013★ 1 cited

Distance-two coloring of sparse graphs

Zdenek Dvorak, Louis Esperet

Consider a graph $G = (V, E)$ and, for each vertex $v \in V$ , a subset $Σ (v)$ of neighbors of $v$ . A $Σ$ -coloring is a coloring of the elements of $V$ so that vertices appearing to…

math.CO2013★ 7 cited

Untangling two systems of noncrossing curves

Jiří Matoušek, Eric Sedgwick, Martin Tancer +1

We consider two systems of curves $(α_{1}, ..., α_{m})$ and $(β_{1}, ..., β_{n})$ drawn on a compact two-dimensional surface $M$ with boundary. Each $α_{i}$ and each $β_{j}$ is either an arc meeti…

math.CO2013★ 7 cited

A family of Alltop functions that are EA-inequivalent to the cubic function

Joanne L. Hall, Asha Rao, Stephen M. Gagola

Sequences with optimal correlation properties are much sought after for applications in communication systems. In 1980, Alltop (IEEE Trans. Inf. Theory 26(3):350-354, 1980) describ…

math.CO2013★ 1 cited

Binary Linear Codes, Dimers and Hypermatrices

Martin Loebl, Pavel Rytíř

We show that the weight enumerator of any binary linear code is equal to the permanent of a 3-dimensional hypermatrix (3-matrix). We also show that each permanent is a determinant…

math.CO2013★ 5 cited

Homometric sets in trees

Radoslav Fulek, Slobodan Mitrović

Let $G = (V, E)$ denote a simple graph with the vertex set $V$ and the edge set $E$ . The profile of a vertex set $V^{'} \subseteq V$ denotes the multiset of pairwise distances between t…

math.CO2013★ 18 cited

On Multiple Pattern Avoiding Set Partitions

Vít Jelínek, Toufik Mansour, Mark Shattuck

We study classes of set partitions determined by the avoidance of multiple patterns, applying a natural notion of partition containment that has been introduced by Sagan. We say th…

math.CO2013★ 14 cited

Subcubic triangle-free graphs have fractional chromatic number at most 14/5

Zdeněk Dvořák, Jean-Sébastien Sereni, Jan Volec

We prove that every subcubic triangle-free graph has fractional chromatic number at most 14/5, thus confirming a conjecture of Heckman and Thomas [A new proof of the independence r…

Crossing numbers and combinatorial characterization of monotone drawings of Kn​

The Potts model and chromatic functions of graphs

On the Geometric Ramsey Number of Outerplanar Graphs

Directed cycle double covers: structure and generation of hexagon graphs

Ramsey numbers of ordered graphs

On q-Series Identities Related to Interval Orders

Saturated simple and k-simple topological graphs

Immersion in four-edge-connected graphs

Estimating the number of disjoint edges in simple topological graphs via cylindrical drawings

Lower bounds on geometric Ramsey functions

Planar 4-critical graphs with four triangles

3-coloring triangle-free planar graphs with a precolored 8-cycle

Firefighting on square, hexagonal, and triangular grids

A Model Theory Approach to Structural Limits

A unified approach to structural limits, and limits of graphs with bounded tree-depth

Distance-two coloring of sparse graphs

Untangling two systems of noncrossing curves

A family of Alltop functions that are EA-inequivalent to the cubic function

Binary Linear Codes, Dimers and Hypermatrices

Homometric sets in trees

On Multiple Pattern Avoiding Set Partitions

Subcubic triangle-free graphs have fractional chromatic number at most 14/5

Crossing numbers and combinatorial characterization of monotone drawings of $K_{n}$

Saturated simple and $k$ -simple topological graphs