Düzlemsel çizgelerin 2-uzaklı renklendirmesi
Küçük Resim Yok
Tarih
2025
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Düzce Üniversitesi
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Bir çizgede, kom¸su kö¸selerin farklı renk alması ko¸suluyla yapılan tüm kö¸selerin renklendirmesine kö¸se renklendirme denir. 2-uzaklı renklendirme ise, yalnızca kom¸su kö¸ selerin de˘ gil, aynı zamanda ortak bir kom¸suya sahip olan (birbirine 2-uzaklıkta bulunan) kö¸selerin de farklı renk almasıyla olu¸ sturulan bir renklendirme türüdür. Bir G çizgesinin 2-uzaklı renklendirmesinde kullanılan en az renk sayısına çizgenin 2-uzaklı renklendirme sayısı denir ve χ2(G) ile gösterilir. Çizgenin çevrim parametresi, içerdi˘ gi en kısa döngünün uzunlu˘guna kar¸sılık gelmektedir. Me¸shur Dört Renk Teoremi'ne göre, bir düzlemsel çizgenin klasik kö¸se renklendirmesi için 4 renk yeterlidir. Ancak, 2-uzaklı renklendirme söz konusu oldu˘ gunda bu sayı çok daha büyük de˘ gerlere ula¸sabilmektedir. Bu çalı¸smada, çevrim parametresi en az 5 olan düzlemsel çizgeler ele alınmı¸s ve maksimum derece ∆(G) ≥ 12 oldu˘gunda, χ2(G) ≤ ∆(G)+5 oldu˘gu ispatlanmı¸stır. Elde edilen bu sonuç, literatürde Zhu ve Bu [4] tarafından elde edilen sonucu iyile¸stirmektedir
A vertex coloring of a graph refers to an assignment of colors to all vertices such that adjacent vertices receive different colors. 2-distance coloring is a type of coloring in which not only adjacent vertices but also vertices that are at a distance of 2 (i.e., those sharing a common neighbor) receive different colors. The minimum number of colors required for a 2-distance coloring of a graph G is called the 2-distance chromatic number and is denoted by χ2(G). The girth of a graph corresponds to the length of its shortest cycle. According to the famous Four Color Theorem, 4 colors are sufficient for the classical vertex coloring of a planar graph. However, for 2-distance coloring, this number can be significantly larger. In this study, we consider planar graphs with girth at least 5, and we prove that χ2(G) ≤ ∆(G)+5 when the maximum degree ∆(G)≥12. This result improves upon the previously known result by Zhu and Bu [4].
A vertex coloring of a graph refers to an assignment of colors to all vertices such that adjacent vertices receive different colors. 2-distance coloring is a type of coloring in which not only adjacent vertices but also vertices that are at a distance of 2 (i.e., those sharing a common neighbor) receive different colors. The minimum number of colors required for a 2-distance coloring of a graph G is called the 2-distance chromatic number and is denoted by χ2(G). The girth of a graph corresponds to the length of its shortest cycle. According to the famous Four Color Theorem, 4 colors are sufficient for the classical vertex coloring of a planar graph. However, for 2-distance coloring, this number can be significantly larger. In this study, we consider planar graphs with girth at least 5, and we prove that χ2(G) ≤ ∆(G)+5 when the maximum degree ∆(G)≥12. This result improves upon the previously known result by Zhu and Bu [4].
Açıklama
Anahtar Kelimeler
Matematik, Mathematics
