The odd distance graph

Kdy? 12.4.2011 10:15 - 11:15
Kde? ZČU / FAV / KMA / UL610 (učebna)
Kategorie

M. Rosenfeld: The odd distance graph

 

 

Abstract: The odd distance graph in Rd is the infinite graph
whose vertices are the points of the Euclidean space Rd and
edges between points whose Euclidean distance is an odd integer.

The odd distance graph in the plane is a natural extension of
the famous unit distance graph. The odd distance graph does not contain
K4 as a subgraph. So like the unit distance graph we are led to
the question whether one can color it with a finite number of colors.

We prove that its chromatic number is at least
five, its list chromatic number is \aleph_0 while the list chromatic
number of the odd distance graph in R3 is not countable. We show that
the Turan graph Tn,3 is embeddable in the odd distance graph in R2
and thus determine the maximum number of odd integer distances among
n points in R2.

We conclude with related open problems.
=============================================================
Joint work with:
Hayri Ardal, Janus Manuch, Moshe Rosenfeld, Saharon Shelah,
Ladislav Stacho.
==============================================================

Evropská unie, ESF, MŠMT, OP Vzdělávání pro konkurenceschopnost, ZČU

Vyhledávání

RSS kanál

Chcete mít stále aktuální přehled toho, co se chystá? Přidejte si náš kanál s přehledem chystaných událostí do Vaší RSS čtečky.