Лінійний ліс

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

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

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

Примітки

1. van der Holst, Lovász, Schrijver, 1999, с. 29–85.
2. Alon, 1988, с. 311–325.
3. Yuster, 1998, с. 293–297.

Література

• Hein van der Holst, László Lovász, . 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.