Лінійний ліс

Лінійний ліс — це вид лісу, утвореного з диз'юнктного об'єднання шляхів. Це орієнтований граф, що не має циклів, у якому кожна вершина має степінь, що не перевищує трьох. Лінійні ліси — це те саме, що й ліси без клешень. Це також графи, інваріант Колен де Вердьєра яких не перевищує 1Шаблон:Sfn.

Лінійна деревність графа — це найменша кількість лінійних лісів, на які можна розкласти цей граф. Для графа з найбільшим степенем $\mathrm{\Delta }$ лінійна деревність завжди не менше $\lceil \mathrm{\Delta }/2\rceil$, і є гіпотеза, що вона завжди не перевершує $\lfloor (\mathrm{\Delta }+1)/2\rfloor$Шаблон:Sfn.

Лінійне розфарбування графа — це власне розфарбування графа, в якому породжений підграф, утворений будь-якими двома кольорами, утворює лінійний ліс. Лінійне хроматичне число графа — це найменша кількість кольорів, що використовуються для будь-якого лінійного розфарбування. Лінійне хроматичне число як максимум пропорційне ${\mathrm{\Delta }}^{3/2}$ (де $\mathrm{\Delta }$ — найбільший степінь графа) і є графи, для яких воно щонайменше пропорційне цій величиніШаблон:Sfn.

Література

• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття