PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 226 | 2 | 173-199
Tytuł artykułu

On generalized shift graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
In 1968 Erdős and Hajnal introduced shift graphs as graphs whose vertices are the k-element subsets of [n] = {1,...,n} (or of an infinite cardinal κ ) and with two k-sets $A = {a₁,...,a_{k}}$ and $B = {b₁,...,b_{k}}$ joined if $a₁ < a₂ = b₁ < a₃ = b₂ < ⋯ < a_k = b_{k-1} < b_k$. They determined the chromatic number of these graphs. In this paper we extend this definition and study the chromatic number of graphs defined similarly for other types of mutual position with respect to the underlying ordering. As a consequence of our result, we show the existence of a graph with interesting disparity of chromatic behavior of finite and infinite subgraphs. For any cardinal κ and integer l, there exists a graph G with |V(G)| = χ(G) = κ but such that, for any finite subgraph F ⊂ G, $χ(F)≤ log_{(l)}|V(F|$, where $log_{(l)}$ is the l-iterated logarithm. This answers a question raised by Erdős, Hajnal and Shelah.
Słowa kluczowe
Rocznik
Tom
226
Numer
2
Strony
173-199
Opis fizyczny
Daty
wydano
2014
Twórcy
  • Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30303, U.S.A.
  • Faculty of Mathematics and CS, Adam Mickiewicz University, 61-614 Poznań, Poland
  • Department of Mathematics and CS, Emory University, Atlanta, GA 30322, U.S.A.
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_4064-fm226-2-6
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.