Лінійний ліс

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

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

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

Література

• Hein van der Holst, László Lovász, Alexander Schrijver. The Colin de Verdière graph parameter // Graph Theory and Combinatorial Biology (Balatonlelle, 1996). — Budapest : János Bolyai Math. Soc, 1999. — Т. 7. — (Bolyai Soc. Math. Stud.)
• Noga Alon. The linear arboricity of graphs // Israel Journal of Mathematics. — 1988. — Т. 62, вип. 3. — DOI:10.1007/BF02783300.
• Raphael Yuster. Linear coloring of graphs // Discrete Mathematics. — 1998. — Т. 185, вип. 1-3. — DOI:10.1016/S0012-365X(97)00209-4.