Книга (теорія графів)

Один вид, який можна назвати книгою чотирикутників, складається з p чотирикутників, що мають спільне ребро (відоме як «корінець» або «база» книги). Тобто це прямий добуток зірки і окремого ребра[1]. 7-сторінкова книга цього типу є прикладом графу без гармонійної розмітки[1].

Другий вид, який можна назвати книгою трикутників або трикутною книгою, є повним двочастковим графом K_1,1,p. Це граф, що складається з ${\displaystyle p}$ трикутників, що мають спільне ребро[2]. Книга цього типу є розщеплюваним графом. Цей граф можна також назвати ${\displaystyle K_{e}(2,p)}$[3]. Книги трикутників утворюють один з ключових блоків реберно-досконалих графів[4].

Термін «граф-книга» використовувався для інших цілей. Так, Баріолі[5] використовував його для графів, складених з довільних підграфів, що мають дві спільні вершини. (Баріолі для цих графів-книг не використовував позначення ${\displaystyle B_{p}}$.)

Якщо дано граф ${\displaystyle G}$, можна записати ${\displaystyle bk(G)}$ для найбільшої книги (розглянутого типу), що міститься в ${\displaystyle G}$.

Позначивши число Рамсея двох трикутних книг ${\displaystyle r(B_{p},\ B_{q}).}$ Це найменше число ${\displaystyle r}$, таке, що для будь-якого графу з ${\displaystyle r}$ вершинами або сам граф містить ${\displaystyle B_{p}}$ як підграф, або його доповнення містить ${\displaystyle B_{q}}$ як підграф.

• Якщо ${\displaystyle 1\leqslant p\leqslant q}$, то ${\displaystyle r(B_{p},\ B_{q})=2q+3}$ (довели Руссо і Шихан).
• Існує стала ${\displaystyle c=o(1)}$, така, що ${\displaystyle r(B_{p},\ B_{q})=2q+3}$, коли ${\displaystyle q\geqslant cp}$.
• Якщо ${\displaystyle p\leqslant q/6+o(q)}$ і ${\displaystyle q}$ досить велике, число Рамсея задається формулою ${\displaystyle 2q+3}$.
• Нехай ${\displaystyle C}$ — стала, і ${\displaystyle k=Cn}$. Тоді будь-який граф з ${\displaystyle n}$ вершинами і ${\displaystyle m}$ ребрами містить книгу трикутників ${\displaystyle B_{k}}$[6].