A new 3-color criterion for planar graphs (K. Diks, L. Kowalik, M. Kurowski) (zadáno)
The union of Balls and its dual shape (H. Edelsbrunner) (zadáno)
Girth of sparse graphs (B. Bollobás and E. Szemerédi) 7 stran. (V článku se zkoumá horní hranice pro obvod grafu na n vrcholech s n+k hranami). (zadáno)
A Ramsey-type problem and the Turán numbers (N. Alon, P. Erdös, D. S. Gunderson, M. Molloy) 10 stran. (V článku se zkoumá varianta Ramseyova problému, kdy chceme nalézt dostatečně velké n, aby v každém hranovém k-obarvení úplného grafu na n vrcholech byl úplný podgraf na m vrcholech obarven nejvýše k-1 barvami.)
Acyclic list 7-coloring of planar graphs (O. V. Borodin, D. G. Fon-Der Flaass, A. V. Kostochka, A. Raspaud, E. Sopena) 8 stran. (Acyklické barvení grafu je takové obarvení vrcholů, že libovolné dvě barevné třídy indukují v grafu les, t.j. podgraf bez cyklů. V článku je ukázáno, že pokud má rovinný graf předepsáno 7 barev u každého vrcholu, lze z nich vybrat acyklické obarvení. Metoda používá tzv. "discharging" - česky bychom řekli "vybíjení náboje" - a rozbor případů).
M. Klazar k referování nabízí následující články. Jsou vytištěné u mě nebo si je lze stáhnout (či prohlédnout) pomocí Science Direct (odkaz je ve formě loga na stránce knihovny MFF).
J. Balogh: The Turán Density of Triple Systems Is Not Principal -
Journal of Combinatorial Theory, Series A 100, 176-180 (2002). (zadáno)
Turánova hustota množiny grafů F je limita zlomků (n
jde
do nekonečna) lim ex(n, F) / (n(n-1)/2), kde ex(n, F)
je
maximální počet hran v jednoduchém grafu na n vrcholech neobsahujícím
jako podgraf žádný graf z F. Erdös-Stone-Simonovitsova věta říká,
že tato hustota se rovná 1-1/(p+1), kde p je nejmenší chromatické
číslo grafu z F. Speciálně je T. hustota množiny grafů F rovna
nejmenší T. hustotě grafu z F. V této poznámce se ukazuje, že to
neplatí pro 3-regulární hypergrafy (systémy trojic). Sestrojí se systém
trojic F, který má T. hustotu menší než každý jeho člen.
S. Gravier, F. Maffray and B. Mohar: On a list-coloring problem -
Discrete Mathematics, Article In Press (6 stran). (zadáno)
Zkoumá se funkce f(G), která je pro graf G definovaná
jako nejmenší číslo k takové, že join G a nezávislé množiny
s k vrcholy není |V(G)|-vybíravý. Join dvou grafů G a
H
vznikne
tak, že se G a H vezmou na dvou disjunktních množinách, které
se pak spojí všemi možnými hranami. Graf G je p-vybíravý,
pokud pro každé přiřazení p-prvkových množin barev k vrcholům G
existuje
funkce, která z každé množiny vybírá barvu tak, že vrcholy spojené hranou
mají vždy různou barvu. Vybíravost G je nejmenší
p, že G
je
p-vybíravý
(je to zobecnění barevnosti a chromatického čísla). .
P. F. Blanchard: On Regressive Ramsey Numbers - Journal of Combinatorial
Theory, Series A 100, 189-195 (2002).
Pro číslo n z N (přirozená čísla) položíme
[n]
= {1, 2, ..., n} a pro libovolnou množinu X symbol [X]^k
označuje
množinu k-prvkových podmnožin X. Funkce f
z [X]^k
do
N,
kde X je podmnožina N, je regresivní pokud pro každou
A
z
[X]^k
je f(A) menší než každý prvek A. Regresivní Ramseyovo číslo
Reg^n(k) se definuje jako nejmenší přir. číslo m
takové, že
pro každou regresivní fukci
f z [m]^n
do N
existuje podmnožina H
množiny
[m] taková, že má alespoň k
prvků
a f zúžená na [H]^n
závisí jen na nejmenším prvku
n-bodovky
v argumentu (tj. když
A a
B
jsou z [H]^n a min(A)
= min(B), potom f(A) = f(B)). V této poznámce se ukazuje, že
Reg^2(5)
= 15, Reg^3(5) = 8, Reg^4(6) = 15, Reg^5(7) > 35
a 194 < Reg^2(6)
< 5.2^{42} + 2^{39} - 1.
P. Komjáth and J.H. Schmerl: The Two Points Theorem of Mazurkiewicz
- Journal of Combinatorial Theory, Series A 99, 371-376 (2002). (zadáno)
V r. 1914 S. Mazurkiewicz dokázal, že existuje podmnožina roviny, která
protíná každou přímku v právě dvou bodech. Autoři Mazurkiewiczovu větu
zobecňují pro každý vektorový prostor nad nekonečným tělesem. Speciálně
platí pro každý Eukleidovský prostor R^d.
duben 2003