Линейный лес

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

Расширения обозначений

По мнению Хабиба и Пероша, k-линейный лес состоит из путей, состоящих из k или меньшего количества узлов каждый.

По мнению Берра и Робертса, (n,j)-линейный лес имеет n вершин, а j входящих в него путей имеет нечетное число вершин.

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

Производные концепции

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

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