Линейный лес

В теории графов , разделе математики , линейный лес — это вид леса , в котором каждый компонент является графом путей , ^{[1] : 200} или несвязным объединением нетривиальных путей. ^{[2] : 246} Эквивалентно, это ациклический граф без клешней . ^{[3] : 130, 131} Ациклический граф, в котором каждая вершина имеет степень 0, 1 или 2, является линейным лесом. ^{[4] : 310  [5] : 107} Неориентированный граф имеет инвариант графа Колена де Вердьера не более 1 тогда и только тогда, когда он является (узловым) несвязным объединением путей, т. е. он линейный. ^{[6] : 13, 19–21  [7] : 29, 35, 67 (3, 6, 29)} Любой линейный лес является подграфом графа путей с тем же числом вершин. ^{[8] : 55}

По мнению Хабиба и Пероша, k -линейный лес состоит из путей, каждый из которых содержит k или меньше узлов. ^{[9] : 219}

По мнению Берра и Робертса, ( n , j )-линейный лес имеет n вершин, а j его составляющих путей имеют нечетное число вершин. ^{[2] : 245, 246}

Согласно Фодри и др., ( k , t )-линейный или ( k , t , s )-линейный лес имеет k ребер и t компонентов, из которых s являются отдельными вершинами; s опускается, если его значение не критично. ^{[10] : 1178, 1179}

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

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