Линейный лес — это вид леса , образованного из дизъюнктного объединения путей . Это ориентированный граф , не имеющий циклов , в котором каждая вершина имеет степень , не превосходящую трёх. Линейные леса — это то же самое, что и леса без клешенй . Это также графы, инвариант Колен де Вердьера которых не превосходит 1 .

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

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

Примечания

Литература