Concept

Hadwiger conjecture (graph theory)

Related publications (6)

Minimal graphs for 2-factor extension

Let G = (V, E) be a simple loopless finite undirected graph. We say that G is (2-factor) expandable if for any non-edge uv, G + uv has a 2-factor F that contains uv. We are interested in the following: Given a positive integer n = vertical bar V vertical b ...

ELSEVIER2020

Monochromatic cycle covers in random graphs

Dániel József Korándi

A classic result of Erdos, Gyarfas and Pyber states that for every coloring of the edges of K-n with r colors, there is a cover of its vertex set by at most f(r)=O(r2logr) vertex-disjoint monochromatic cycles. In particular, the minimum number of such cove ...

WILEY2018

The Erdos-Hajnal conjecture for rainbow triangles

János Pach

We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order ohm(n(1/3) log(2) n) which uses at most two colors, and this bound is tight up to a constant factor. This verifies a conjectu ...

Academic Press Inc Elsevier Science2015

Design and Optimization of Orthogonally Intersecting Planar Surfaces

Mark Pauly, Yuliy Gennadievich Schwartzburg

We present a method for the design of 3D constructions from planar pieces that can be cut easily and cheaply with laser cutters and similar Computer Numerical Control (CNC) machines. By cutting tight slits in intersecting pieces, they can be slid into each ...

Springer Berlin Heidelberg2012

A bipartite strengthening of the Crossing Lemma

János Pach

Let G = (V, E) be a graph with n vertices and m >= 4n edges drawn in the plane. The celebrated Crossing Lemma states that G has at least Omega(m(3)/n(2)) pairs of crossing edges; or equivalently, there is an edge that crosses Omega(m(2)/n(2)) other edges. ...

2010

Survivable Routing of Mesh Topologies in IP-over-WDM Networks by Recursive Graph Contraction

Patrick Thiran, Maciej Kurant

Failure restoration at the IP layer in IP-over-WDM networks requires to map the IP topology on the WDM topology in such a way that a failure at the WDM layer leaves the IP topology connected. Such a mapping is called survivable. Finding a survivable mappin ...

2007