Χ sınırlı - Χ-bounded

İçinde grafik teorisi, bir ${ displaystyle chi}$sınırlı aile ${ displaystyle { mathcal {F}}}$ Grafiklerin oranı, bazı işlevleri olan bir grafiktir ${ displaystyle c}$ öyle ki her tam sayı için ${ displaystyle t}$ içindeki grafikler ${ displaystyle { mathcal {F}}}$ hayır ile ${ displaystyle t}$-vertex klik olabilir renkli en fazla ${ displaystyle c (t)}$ renkler. Bu kavram ve gösterimi, András Gyárfás.^[1] Yunan harfinin kullanımı chi dönem içinde ${ displaystyle chi}$-bounded, kromatik sayı bir grafiğin ${ displaystyle G}$ yaygın olarak belirtilir ${ displaystyle chi (G)}$.

Önemsizlik

Tüm grafiklerin ailesinin olduğu doğru değil ${ displaystyle chi}$sınırlı.As Zykov (1949) ve Mycielski (1955) gösterdi, var üçgen içermeyen grafikler keyfi olarak büyük kromatik sayı,^[2][3] bu nedenle bu grafikler için sonlu bir değer tanımlamak mümkün değildir ${ displaystyle t (3)}$.Böylece, ${ displaystyle chi}$-sınırlılık, bazı grafik aileleri için geçerli ve diğerleri için yanlış olan önemsiz bir kavramdır.^[4]

Belirli sınıflar

Sınırlı her sınıf grafik kromatik sayı (önemsiz) ${ displaystyle chi}$sınırlı ${ displaystyle c (t)}$ kromatik sayı üzerindeki sınıra eşittir. Bu, örneğin, düzlemsel grafikler, iki parçalı grafikler ve sınırlı grafikler yozlaşma. Tamamlayıcı olarak, bağımsızlık numarası sınırlıdır da ${ displaystyle chi}$sınırlı olarak Ramsey teoremi büyük gruplara sahip olduklarını ima eder.

Vizing teoremi şu şekilde yorumlanabilir: Çizgi grafikleri vardır ${ displaystyle chi}$sınırlı ${ displaystyle c (t) = t}$.^[5][6] pençesiz grafikler daha genel olarak da ${ displaystyle chi}$ile sınırlı ${ displaystyle c (t) leq (t-1) ^ {2}}$. Bu, bu grafiklerde, birçok komşusu olan bir tepe noktasının büyük bir kliğin parçası olması gerektiğini göstermek için Ramsey teoremini kullanarak görülebilir.Bu sınır, en kötü durumda neredeyse sıkıdır, ancak birbirine bağlı üç grafiği içeren pençesiz grafikler bitişik olmayan köşelerin kromatik sayısı daha da küçüktür, ${ displaystyle c (t) = 2 (t-1)}$.^[5]

Diğer ${ displaystyle chi}$Sınırlı grafik aileleri şunları içerir:

• mükemmel grafikler, ile ${ displaystyle c (t) = t-1}$
• Grafikleri kutsılık iki^[7]
• Sınırlı grafikler klik genişliği^[8]
• kavşak grafikleri düzlemdeki herhangi bir kompakt dışbükey şeklin ölçeklenmiş ve çevrilmiş kopyalarının^[9]
• daire grafikler ve (daire grafiklerini genelleştirerek) "dış ip grafikleri", düzlemdeki sınırlı eğrilerin kesişim grafikleri aranjman eğrilerin^[10]

Bununla birlikte, dışbükey şekillerin kesişme grafikleri, daire grafikleri ve dış sicim grafiklerinin tümü, dize grafikleri, dize grafiklerinin kendileri ${ displaystyle chi}$Sınırlı. Özel bir durum olarak aşağıdaki kesişim grafiklerini içerirler. doğru parçaları, bunlar da değil ${ displaystyle chi}$sınırlı.^[4]

Çözülmemiş sorunlar

Matematikte çözülmemiş problem: Tüm ağaçsız grafik sınıfları ${ displaystyle chi}$sınırlı mı? (matematikte daha fazla çözülmemiş problem)

Göre Gyárfás – Sumner varsayımı her biri için ağaç ${ displaystyle T}$, içermeyen grafikler ${ displaystyle T}$ olarak indüklenmiş alt grafik vardır ${ displaystyle chi}$sınırlı. Örneğin, pençe özel bir ağaç türü olduğu için bu, pençesiz grafikler için geçerliydi, ancak varsayımın yalnızca bazı özel ağaçlar için doğru olduğu bilinmektedir. yollar^[1] ve yarıçap-iki ağaç.^[11]

Çözülmemiş başka bir sorun ${ displaystyle chi}$-bounded, her kalıtsal grafik sınıfının olup olmadığını soran Louis Esperet tarafından ortaya atıldı. ${ displaystyle chi}$-bounded bir işleve sahiptir ${ displaystyle c (t)}$ en fazla polinomik olarak büyüyen ${ displaystyle t}$.^[6]

Matematikte çözülmemiş problem: Kalıtsal olarak ${ displaystyle chi}$-bounded grafik sınıfı, kromatik sayı klik boyutunda en çok polinom mudur? (matematikte daha fazla çözülmemiş problem)

Referanslar

Dış bağlantılar

• Ki-sınırlı, Açık Problem Bahçesi