Skip to main content
فهرست مقالات

-λرنگ آمیزی برخی از گرافها و حدس ∆^2

نویسنده:

(8 صفحه - از 59 تا 66)

ﺑﻪ ﺍﺯﺍﻱ ﮔﺮﺍﻑ ﺩﺍﺩﻩ ﺷﺪﻩ 𝐺، ﺗﻮﺍﻥ ﺩﻭﻡ ﮔﺮﺍﻑ 𝐺، ﮐﻪ ﺑﺎ 𝐺2 ﻧﺸﺎﻥ ﺩﺍﺩﻩ ﻣﻲﺷﻮﺩ، ﮔﺮﺍﻓﻲ ﺍﺳﺖ ﺑﺎ ﻣﺠﻤﻮﻋﻪ ﺭﺋﻮﺱ 𝑉 ﺑﻪ ﻃﻮﺭﻳﮑﻪ ﺩﻭ ﺭﺍﺱ ﺩﺭ ﺍﻳﻦ ﮔﺮﺍﻑ ﻣﺠﺎﻭﺭﻧﺪ ﺍﮔﺮ ﻭ ﺗﻨﻬﺎ ﺍﮔﺮ ﻓﺎﺻﻠﻪ ﺍﻳﻦ ﺩﻭ ﺭﺍﺱ ﺩﺭ𝐺 ﺣﺪﺍﮐﺜﺮ 2 ﺑﺎﺷﺪ. ﮔﺮﺍﻑ 𝐺 ﺭﺍ ﻣﺮﺑﻌﻲ ﮔﻮﻳﻴﻢ ﻫﺮﮔﺎﻩ ﮔﺮﺍﻓﻲ ﻣﺎﻧﻨﺪ 𝐻 ﻭﺟﻮﺩ ﺩﺍﺷﺘﻪ ﺑﺎﺷﺪ ﺑﻪﻃﻮﺭﻳﮑﻪ، 𝐻2 . ﺗﺎﺑﻊ 𝑓 ﺭﺍ ﻳﮏ λ−ﺭﻧﮓ ﺁﻣﻴﺰﻱ ﺍﺯ 𝐺 ﻣﻲﻧﺎﻣﻴﻢ ﻫﺮﮔﺎﻩ ﺑﺮﺍﻱ ﻫﺮ ﺩﻭ ﺭﺍﺱ 𝑥, 𝑦 ∈ 𝑉 ﺑﺎ 1 = )𝑑(𝑥, 𝑦 ﺩﺍﺷﺘﻪ ﺑﺎﺷﻴﻢ 2 ≥ |)𝑓(𝑥) − 𝑓(𝑦| ﺑﻪ ﻋﻼﻭﻩ ﺍﮔﺮ 2 = 𝑑(𝑥, 𝑦 )، ﺁﻧﮕﺎﻩ 1 ≥ |)𝑓(𝑥) − 𝑓(𝑦|. ﮐﻤﺘﺮﻳﻦ ﻣﻘﺪﺍﺭ 𝑘 ﮐﻪ ﺑﻪ ﺍﺯﺍﻱ ﺁﻥ ﻳﮏ λ−ﺭﻧﮓ ﺁﻣﻴﺰﻱ ﺍﺯ 𝐺 ﻭﺟﻮﺩ ﺩﺍﺷﺘﻪ ﺑﺎﺷﺪ ﺭﺍ ﺑﺎ 𝜆 ﻧﺸﺎﻥ ﻣﻲﺩﻫﻴﻢ. ﺩﺭ ﺳﺎﻝ ۱۹۹۳ ﮔﺮﻳﮑﺲ ﻭ ﻳﻪ ﺣﺪﺱ ﺯﺩﻧﺪ ﺍﮔﺮ 𝐺 ﮔﺮﺍﻓﻲ ﺑﺎ ﻣﺎﮐﺴﻴﻤﻢ ﺩﺭﺟﻪ 2 ≥∆ ﺑﺎﺷﺪ، ﺁﻧﮕﺎﻩ 𝜆(𝐺) ≤ ∆2. ﺩﺭ ﺍﻳﻦ ﻣﻘﺎﻟﻪ، ﺿﻤﻦ ﺍﺭﺍﺋﻪ ﮐﺮﺍﻥﻫﺎﻳﻲ ﺑﺮﺍﻱ λ−ﺭﻧﮓ ﺁﻣﻴﺰﻱ ﮔﺮﺍﻑﻫﺎ، ﺣﺪﺱ ﻣﺬﮐﻮﺭ ﺭﺍ ﺑﺮﺍﻱ ﮔﺮﺍﻑﻫﺎﻱ ﻣﺮﺑﻌﻲ، ﮔﺮﺍﻑﻫﺎﻱ ﺧﻄﻲ ﻭ ﮔﺮﺍﻑﻫﺎﻱ ﻓﺎﻗﺪ ﻣﺎﻳﻨﻮﺭ ﮔﺮﺍﻑﻫﺎﻱ ﮐﺎﻣﻞ 𝐾4 ﻭ 𝐾5 ﺍﺛﺒﺎﺕ ﺧﻮﺍﻫﻴﻢ ﮐﺮﺩ.


برای مشاهده محتوای مقاله لازم است وارد پایگاه شوید. در صورتی که عضو نیستید از قسمت عضویت اقدام فرمایید.