Линейный лес - Википедия - Linear forest

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

В линейная древовидность графа - это минимальное количество линейных лесов, на которые можно разбить граф. Для графика максимальной степени , линейная древовидность всегда не меньше , и предполагается, что всегда не более .[2]

Линейная раскраска графа - это собственная раскраска графика в которой индуцированный подграф Каждые два цвета образуют линейный лес. Линейное хроматическое число графа - это наименьшее количество цветов, используемых в любой линейной раскраске. Линейное хроматическое число не более чем пропорционально , и существуют графики, для которых она хотя бы пропорциональна этой величине.[3]

Рекомендации

  1. ^ ван дер Хольст, Хайн; Ловас, Ласло; Шрайвер, Александр (1999), "Параметр графа Колена де Вердьера", Теория графов и комбинаторная биология (Балатонлелле, 1996), Bolyai Soc. Математика. Stud., 7, Будапешт: János Bolyai Math. Soc., Стр. 29–85..
  2. ^ Алон, Н. (1988), «Линейная древовидность графов», Израильский математический журнал, 62 (3): 311–325, CiteSeerX  10.1.1.163.1965, Дои:10.1007 / BF02783300, МИСТЕР  0955135.
  3. ^ Юстер, Рафаэль (1998), "Линейная раскраска графов", Дискретная математика, 185 (1–3): 293–297, Дои:10.1016 / S0012-365X (97) 00209-4, МИСТЕР  1614290.