Libro (grafeoteorio)

eta
En grafeoteorio, libro (kutime uzata notacio: Bp) estas fendebla grafeo konsistanta el p cikloj havantaj komunan lateron, kiun oni nomas la "bazo" de la libro. Por la plej granda libro enhavata en G oni ofte uzas notacion bk(G).

Antaŭe, la libro estadis skribata kiel Ke(2, p). Estu K(m, n) la plena dukolora grafeo kun ampleksoj de la koloraj partoj m kaj n. Tiam Ke(m, n) estas difinita kiel K(m, n) kun superflua latero en la unua dispartigo. Ĝi povas ankaŭ esti konsiderata kiel plena trikolora grafeo K(1, 1, p).

 Ecoj 

Ĉi tie r(Bp, Bq) estas la nombro de Ramsey inter du libroj.

 Se 1≤p≤q, tiam r(Bp, Bq)=2q+3 (pruvita de Rousseau kaj Sheehan).
 Ekzistas konstanto c=o(1) tia, ke, se cp ≤q , tiam r(Bp, Bq)=2q+3.
 Se p≤q/6+o(q) kaj q estas granda, tiam r(Bp, Bq)=2q+3.
 Estu C konstanto kaj k = Cn. Tiam ĉiu grafeo kun n verticoj kaj m lateroj enhavas Bk. (???)

Kategorio:Grafeteorio