Сызықтық орман - Википедия - Linear forest

Жылы графтар теориясы, математика бөлімі, а сызықтық орман түрі болып табылады орман бастап қалыптасқан бірлескен одақ туралы жол графиктері. Бұл бағытталмаған граф жоқ циклдар онда әрқайсысы шың бар дәрежесі ең көп дегенде екі. Сызықтық ормандар - бұл бірдей нәрсе тырнақсыз ормандар. Олар кімнің графиктері Колин де Вердиер графигі өзгермейді ең көбі 1.[1]

The сызықтық ағаштылық график - бұл графикті бөлуге болатын сызықтық ормандардың минималды саны. Максималды дәреже графигі үшін , сызықтық арборит әрқашан кем дегенде болады және бұл әрқашан ең көп деп болжанады .[2]

Графиктің сызықтық бояуы дұрыс болып табылады графикалық бояу онда индукцияланған субография әр екі түстен құралған - бұл түзу орман. Графиктің сызықтық хроматикалық саны - кез-келген сызықтық бояумен қолданылатын түстердің ең аз саны. Сызықтық хроматикалық сан ең көп дегенде пропорционалды және графиктер бар, олар үшін ол кем дегенде осы мөлшерге пропорционалды болады.[3]

Әдебиеттер тізімі

  1. ^ ван дер Холст, Хейн; Ловас, Ласло; Шрайвер, Александр (1999), «Colin de Verdière графикалық параметрі», Графика теориясы және комбинаторлық биология (Balatonlelle, 1996), Боляй Соц. Математика. Stud., 7, Будапешт: Янош Боляй Математика. 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.