Линейный лес - Linear forest - Wikipedia

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

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

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

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

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

[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.

[1]

[2]

[3]