Kenar boyama - Edge coloring

Desargues grafiğinin 3 kenarlı renklendirmesi

Olarak grafik teorisi , bir boyama kenarı a grafik hiçbir iki olay kenarları aynı renkte olduğu, böylece grafik kenarlarına "renk" bir görevdir. Örneğin, sağdaki şekil, kırmızı, mavi ve yeşil renklerle bir grafiğin kenar renklendirmesini gösterir. Kenar renklendirmeleri, birkaç farklı grafik renklendirme türünden biridir . Kenar boyama sorunu en az kullanarak belirli bir grafik kenarlarını renk mümkün olup olmadığını sorar $k$ belirli bir değeri için farklı renkler, $k$ , ya da en muhtemel renk değişimi ile. Belirli bir grafiğin kenarları için gereken minimum renk sayısına, grafiğin kromatik indeksi denir . Örneğin, çizimdeki grafiğin kenarları üç renkle renklendirilebilir, ancak iki renkle renklendirilemez, bu nedenle gösterilen grafiğin kromatik indeksi üçtür.

Tarafından Vizing teoremi , basit grafik kenar renk için gereken renklerin sayısı, en fazla, ya bir derece $Δ$ veya $Δ + 1$ . Gibi bazı grafikler için, iki taraflı grafikler ve yüksek derecede düzlemsel grafikler , renk sayısı her zaman $Δ$ ve için multigraphs , renk sayısı kadar büyük olabilir $3Δ / 2$ . İki parçalı grafiklerin optimal renklerini oluşturan polinom zaman algoritmaları ve en fazla $Δ+1$ renk kullanan iki parçalı olmayan basit grafiklerin renklendirmeleri vardır; bununla birlikte, optimal bir kenar renklendirme bulmanın genel sorunu NP-zordur ve bunun için bilinen en hızlı algoritmalar üstel zaman alır. Kenarlara renk atamalarının bitişik olmama dışındaki koşulları karşılaması gereken kenar renklendirme probleminin birçok varyasyonu incelenmiştir. Kenar renklendirmelerinin, fiber optik ağlar için zamanlama problemlerinde ve frekans atamasında uygulamaları vardır .

Örnekler

Döngünün uzunluğu eşitse , bir döngü grafiğinin kenarları iki renkle renklendirilebilir: basitçe döngü etrafındaki iki rengi değiştirin. Ancak uzunluk tek ise, üç renk gerekir.

Tam grafiğin 7 kenarlı renklendirmesinin geometrik yapısı

K 8

. Yedi renk sınıfının her birinin merkezden çokgen tepe noktasına bir kenarı ve buna dik üç kenarı vardır.

Bir tam grafik $K, n$ ile $n$ noktalar ile kenar renklendirilebilir olan $n 1 -$ renk zaman $, n$ , bir çift sayı bu Baranyai teoreminin özel bir halidir . Soifer (2008) , bu durumda bir renklendirmenin aşağıdaki geometrik yapısını sağlar: $n$ noktayı düzgün $(n - 1)$ kenarlı bir çokgenin köşelerine ve merkezine yerleştirin . Her renk sınıfı için, merkezden çokgen köşelerinden birine bir kenarı ve çokgen köşe çiftlerini birbirine bağlayan tüm dik kenarları ekleyin. Ancak, $n$ tek olduğunda , $n$ renge ihtiyaç duyulur: her renk yalnızca $(n - 1)/2$ kenar için kullanılabilir, bu toplamın $1/ n'lik bir$ kesridir.

Birçok yazar kenarı renklendirici inceledik tek grafikler , $n$ noktalar ekipleri temsil ettiği -Normal grafikler $n 1 -$ havuzundan seçilen oyuncular $2 n 1 -$ ile (çalar ve bu kenarlar, bu takımın muhtemel eşleşmeleri temsil bir oyuncu "garip adam dışarıda" olarak oyuna hakemlik yapmak üzere ayrıldı). Durumda bu $n = 3$ , iyi bilinen verir Petersen grafiği . Gibi (1972) Biggs (Problem açıklıyor $n = 6$ ), oyuncular her takım bütün takımlar için kapalı Pazar günleri ile haftanın farklı günlerinde altı oyunların her oynar öyle ki Bu eşleşmeden için zamanlama bulmak istediğiniz; yani, problemi matematiksel olarak formüle ederek, 6 düzenli tek grafiğin 6 kenarlı rengini bulmak istiyorlar $O 6$ . Zaman $, n$ 3, 4 ya da 8'e ait boyama kenardır $O, n$ gerektirir $, n + 1$ renkler, ancak 5, 6, ya da 7 olduğu zaman, sadece $, n$ renk ihtiyaç vardır.

Tanımlar

Bunu gibi tepe muadili , bir boyama kenar kayıtsız şartsız bahsedilen zaman bir grafik, her zaman için bir iki komşu kenarları aynı renk atanır, yani kenarları uygun bir boyama olduğu varsayılır. Burada, ortak bir köşe paylaştıklarında iki farklı kenar bitişik olarak kabul edilir. Bir grafik renklendirme bir kenar $G$ , aynı zamanda, boyama, bir tepe denk olarak düşünülebilir çizgi grafiğidir $L (G)$ , her bir kenar için bir tepe vardır grafik $G$ ve bitişik kenarların her çift için bir kenar $G$ .

$k$ farklı renkle uygun bir kenar boyamaya (uygun) $k$ -kenar boyama denir . Bir atanabilir bir grafiktir $k$ -kenar-boyama olduğu söylenir $k$ -kenar-renklendirilebilir. Bir grafik bir (uygun) kenar boyama gerekli renk küçük sayı $G$ olduğu renk indeksi , ya da kenar renk numarası $χ '(G)$ . Kromatik indeks de bazen $χ 1 (G)$ notasyonu kullanılarak yazılır ; bu gösterimde, bir alt simge, kenarların tek boyutlu nesneler olduğunu gösterir. Bir grafik, kromatik indeksi tam olarak $k$ ise $k$ -edge-kromatiktir . Renk indeksi ile karıştırılmamalıdır renk sayısı $kay kare testi ($ $G$ $)$ ya da $χ$ $0$ $($ $G$ $)$ , ve boyama uygun bir tepe gerekli renk az sayıda $G$ .

Aksi belirtilmedikçe, iki veya daha fazla kenarın aynı uç nokta çiftini bağlayabildiği ve kendi kendine döngülerin bulunabileceği çoklu grafiklerin aksine, tüm grafiklerin basit olduğu varsayılır . Kenar renklendirmedeki birçok problem için, basit grafikler çoklu grafiklerden farklı davranır ve basit grafiklerin kenar renklendirmeleriyle ilgili teoremleri çoklu grafik durumuna genişletmek için ek özen gerekir.

Eşleştirme ile ilgili

Bu 3-düzenli düzlemsel grafiğin 16 köşesi ve 24 kenarı vardır, ancak herhangi bir maksimum eşleşmede yalnızca 7 kenar vardır. Bu nedenle, herhangi bir kenar renklendirmede dört renk gerektirir.

$G$ grafiğindeki bir eşleşme , ikisi bitişik olmayan bir kenarlar kümesidir; Bir mükemmel eşleme kenarları grafiğin tüm node dokunmadan ve içeren bir uygun olan en uygun mümkün olduğu kadar çok kenarlı olarak aşağıdakileri içeren bir uygun olan. Kenar renklendirmede, herhangi bir renge sahip kenar kümesinin tümü birbirine bitişik olmamalıdır, böylece bir eşleşme oluştururlar. Yani, uygun bir kenar renklendirme, grafiğin ayrık eşleşmelere bölünmesiyle aynı şeydir.

Belirli bir grafikteki maksimum eşleşmenin boyutu küçükse, grafiğin tüm kenarlarını kapsamak için birçok eşleşme gerekecektir. Daha resmi olarak ifade edilirse, bu akıl yürütme, bir grafiğin toplamda $m$ kenarı varsa ve en fazla $β$ kenarı bir maksimum eşleşmeye aitse, o zaman grafiğin her kenar renklendirmesinde en az $m /β$ farklı renkler kullanılması gerektiği anlamına gelir. Örneğin, şekilde gösterilen 16 köşeli düzlemsel grafiğin $m = 24$ kenarı vardır. Bu grafikte mükemmel bir eşleşme olamaz; çünkü merkez tepe noktası eşleştirilirse, kalan eşleşmeyen köşeler dört, beş ve beş köşeli üç farklı bağlantılı bileşende gruplandırılabilir ve tek sayıda köşeye sahip bileşenler tam olarak eşleştirilemez. Bununla birlikte, grafik yedi kenarla maksimum eşleşmeye sahiptir, bu nedenle $β = 7$ . Bu nedenle, grafiği kenar renklendirmek için gereken renk sayısı en az 7/24 ve renk sayısı bir tam sayı olması gerektiğinden en az dörttür.

Mükemmel bir eşleşmeye sahip olmayan düzenli bir $k$ derecesi grafiği için , bu alt sınır, en az $k + 1$ rengin gerekli olduğunu göstermek için kullanılabilir . Özellikle bu, tek sayıda köşesi olan (tek tam grafikler gibi) normal bir grafik için geçerlidir; bu tür grafikler için, el sıkışma lemması ile $k'nin$ kendisi çift olmalıdır. Bununla birlikte, $χ' \geq m /β$ eşitsizliği her düzenli grafiğin kromatik indeksini tam olarak açıklamaz, çünkü mükemmel eşleşmeleri olan ancak k -kenarla renklendirilemeyen düzenli grafikler vardır . Örneğin, Petersen grafiği , mükemmel eşleşmelerinde $m = 15$ ve $β = 5$ kenarlı düzenlidir , ancak 3 kenarlı bir renklendirmeye sahip değildir.

Derece ilişkisi

Vizing teoremi

Bir grafik kenarı renk sayısı $G$ çok yakından ilişkilidir maksimum derecede $Δ (G)$ , herhangi bir tek tepe noktası, kenarları olayın en çok sayıda $G$ . Açıktır ki, $χ'(G) \geq Δ(G)$ , çünkü eğer $Δ$ farklı kenarların hepsi aynı $v '$ de buluşuyorsa , o zaman bu kenarların tümüne birbirinden farklı renkler atanması gerekir ve bu ancak en az $Δ$ renk atanabilir. Vizing'in teoremi (adını 1964'te yayınlayan Vadim G. Vizing'den almıştır) bu sınırın neredeyse sıkı olduğunu belirtir: herhangi bir grafik için kenar kromatik sayı ya $Δ(G)$ ya da $Δ(G) + 1'dir$ . Tüm $χ '(G) = Δ (G)$ , G sınıfı 1 olduğu söylenir; aksi takdirde 2. sınıf olduğu söylenir.

Her iki parçalı grafik sınıf 1'dir ve hemen hemen tüm rasgele grafikler sınıf 1'dir. Bununla birlikte, rastgele bir grafiğin sınıf 1 olup olmadığını belirlemek NP-tamdır .

Vizing (1965) , maksimum dereceden en az sekiz olan düzlemsel grafiklerin birinci sınıf olduğunu kanıtladı ve aynı şeyin maksimum derece yedi veya altı olan düzlemsel grafikler için de geçerli olduğunu tahmin etti. Öte yandan, iki ile beş arasında değişen maksimum dereceli ve ikinci sınıf düzlemsel grafikler vardır. Tahmin, o zamandan beri maksimum derece yedi olan grafikler için kanıtlanmıştır. Köprüsüz düzlemsel kübik grafiklerin tümü 1. sınıftır; bu, dört renk teoreminin eşdeğer bir şeklidir .

Normal grafikler

Bir k - düzenli grafiğin 1-faktörleştirilmesi , grafiğin kenarlarının mükemmel eşleşmelere bölünmesi, grafiğin k -kenar renklendirmesi ile aynı şeydir . Diğer bir deyişle, düzenli bir grafiğin 1 çarpanlara ayırması, ancak ve ancak sınıf 1 ise. Bunun özel bir durumu olarak, bir kübik (3-düzenli) grafiğin 3 kenarlı renklendirmesine bazen Tait renklendirme denir .

Her normal grafiğin 1 çarpanlarına ayırma özelliği yoktur; örneğin, Petersen grafiği yoktur. Daha genel olarak snarklar , Petersen grafiği gibi köprüsüz, 3-düzenli ve 2. sınıf grafikler olarak tanımlanır.

Kőnig'in (1916) teoremine göre , her iki parçalı düzenli grafiğin 1 çarpanlarına ayırması vardır. Teorem daha önce projektif konfigürasyonlar açısından ifade edilmiş ve Ernst Steinitz tarafından kanıtlanmıştır .

çoklu grafikler

Herhangi bir kenar renklendirmesinde dokuz renk gerektiren, derece altı ve kenar çokluğu üç olan bir Shannon çoklu grafiği

İçin multigraphs , burada çok sayıda paralel kenarları aynı iki köşe, Vizing teoremi kenar renk sayısı ile ilgili bilinen olandan benzer fakat daha zayıf olan sonuçları bağlanabilir $( ', x, G)$ , maksimum derecede $Δ (G)$ , ve çokluk $^ ı (G)$ , herhangi bir paralel kenar demetindeki maksimum kenar sayısı. Vizing teoreminin çoklu grafikleri genelleştirmediğini gösteren basit bir örnek olarak, bir Shannon çoklu grafiğini, üç köşe çiftinin her birini birbirine bağlayan üç $μ(G)$ paralel kenar demeti olan bir çoklu grafiği düşünün . Bu örnekte, $Δ(G) = 2μ(G)$ (her köşe, $μ(G)$ paralel kenarların üç demetinden sadece ikisine $denk gelir$ ) ancak kenar kromatik numarası $3μ($ $G$ $)'dir$ ( $3μ(G vardır))$ toplam kenarlar ve her iki kenar bitişiktir, bu nedenle tüm kenarlar birbirine farklı renkler atanmalıdır). Vizing'e ilham veren bir sonuçta, Shannon (1949) bunun en kötü durum olduğunu gösterdi: herhangi bir çoklu grafik $G$ için $χ'(G) \leq (3/2)Δ(G)$ . Ek olarak, herhangi bir çoklu grafik $G için$ , $χ'($ $G$ $) \leq Δ($ $G$ $) + μ($ $G$ $)$ , basit grafikler durumunda Vizing teoremine indirgenen bir eşitsizlik (bunun için $μ($ $G$ $) = 1$ ).

algoritmalar

Bir grafiğin sınıf 1 olup olmadığını test etme sorunu NP-tamamlandı olduğundan, her grafiğin optimal sayıda renkle kenar renklendirmesi için bilinen bir polinom zaman algoritması yoktur. Bununla birlikte, bu kriterlerden bir veya daha fazlasını gevşeten bir dizi algoritma geliştirilmiştir: bunlar yalnızca bir grafik alt kümesi üzerinde çalışırlar veya her zaman optimal sayıda renk kullanmazlar veya her zaman polinom zamanında çalışmazlar.

Özel grafik sınıflarını optimum şekilde renklendirme

İki parçalı grafikler veya maksimum derece $Δ$ olan çoklu grafikler durumunda , optimal renk sayısı tam olarak $Δ'dir$ . Cole, Ost & Schirra (2001) bu grafiklerin optimal kenar renklendirmesinin doğrusala yakın zaman sınırında bulunabileceğini gösterdi $(m log Δ)$ , burada $m$ grafikteki kenarların sayısıdır; daha basit ama biraz daha yavaş algoritmalar Cole & Hopcroft (1982) ve Alon (2003) tarafından tanımlanmıştır . Alon'un (2003) algoritması , giriş grafiğini, derecesini artırmadan veya boyutunu önemli ölçüde artırmadan, bipartisyonun aynı tarafına ait köşe çiftlerini birleştirerek ve ardından az sayıda ek köşe ve kenar ekleyerek düzenli hale getirerek başlar. . Ardından, derece tek ise, Alon doğrusala yakın zamanda tek bir mükemmel eşleşme bulur, ona bir renk atar ve onu grafikten kaldırarak derecenin eşit olmasına neden olur. Son olarak, Alon, Gabow'un (1976) bir gözlemini uygular, grafın bir Euler turunda kenarların değişen alt kümelerini seçmenin , kenar renklendirme problemini iki küçük alt probleme bölmek için onu iki normal alt grafiğe böldüğü ve onun algoritması iki alt problemi çözdüğü gözlemini uygular. özyinelemeli . Algoritması için toplam süre $O(m log m)'dir$ .

İçin düzlemsel grafikler maksimum derecede ile $Ô \geq 7$ , renk optimal sayısı daha tam olarak $Δ$ . $Δ \geq 9$ olduğu daha güçlü varsayımla, lineer zamanda optimal bir kenar renklendirmesi bulmak mümkündür ( Cole & Kowalik 2008 ).

Komşuluk matrislerinin en fazla $d 1-ε$ ikinci en büyük özdeğerine (mutlak değerde) sahip olması anlamında sözde rasgele olan d-düzenli grafikler için d , optimal renk sayısıdır ( Ferber & Jain 2018 ).

Optimum renk sayısından fazlasını kullanan algoritmalar

Misra & Gries (1992) ve Gabow ve diğerleri. (1985) , Vizing teoremi tarafından verilen sınırı karşılayan, herhangi bir grafiği $Δ + 1$ renklerle renklendirmek için polinom zaman algoritmalarını tanımlar ; bkz. Misra & Gries kenar renklendirme algoritması .

Çoklu grafikler için, Karloff ve Shmoys (1987) , Eli Upfal'a atfettikleri aşağıdaki algoritmayı sunar . Her tek dereceli tepe noktasına bir kenarla bağlanan yeni bir tepe noktası ekleyerek giriş multigrafını $G$ Eulerian yapın, bir Euler turu bulun ve tur için bir yön seçin. İki parçalı bir grafik $H oluşturun$ , burada $G'nin$ her bir köşesinde birer tane olmak üzere, ikili bölmenin her iki tarafında birer tane olmak üzere, bir kenarı ikili bölmenin sol tarafındaki bir $u$ köşesinden bölmenin sağ tarafındaki bir $v$ köşesine kadar olan bir çift parçalı grafik oluşturun. yönlendirilmiş tur bir kenara sahip her $u$ için $v$ içinde $G$ . $H$ öğesine iki parçalı bir grafik kenar renklendirme algoritması uygulayın . Her renk sınıfı $H$ kenarların kümesine karşılık gelir $G$ maksimum derecede iki olan bir alt grafiğini oluşturur; ki içinde her bir renk sınıfı için, yollar ve bir döngü ayrık birliği $H$ üç renk sınıfları oluşturmak mümkündür $G$ . Algoritmanın süresi , Cole, Ost & Schirra'nın (2001) algoritması kullanılarak , $O(m log Δ)$ iki parçalı bir grafiği kenar renklendirme süresi ile sınırlıdır . Bu algoritmanın kullandığı renk sayısı en fazla , Shannon'ın sınırına yakın, ancak onunla tamamen aynı değil . Ayrıca basit bir şekilde paralel bir algoritma haline getirilebilir . Aynı makalede, Karloff ve Shmoys, aynı prensipler üzerinde çalışan (Shannon ve Vizing'in sınırlarına uyan) dört renkle maksimum derece üç çoklu grafiklerini renklendirmek için doğrusal bir zaman algoritması sunar: onların algoritması, grafiği Eulerian yapmak için yeni bir tepe noktası ekler, bir Euler turu bulur ve ardından grafiği maksimum derece iki olan iki alt grafiğe bölmek için turda alternatif kenar kümeleri seçer. Her alt grafiğin yolları ve hatta döngüleri, alt grafik başına iki renkle renklendirilebilir. Bu adımdan sonra, kalan her tek döngü, karşıt alt grafiğe ait iki renkten biri ile renklendirilebilen en az bir kenar içerir. Bu kenarı tek döngüden çıkarmak, alt grafiği için iki renk kullanılarak renklendirilebilen bir yol bırakır. $3\sol\lceil {\frac {\Delta }{2}}\sağ\rceil$ $\left\lfloor {\frac {3\Delta }{2}}\sağ\rfloor$

Bir grafiğin veya çoklu grafiğin kenarlarını tek tek ele alan ve her kenara ilk kullanılabilir rengi atayan açgözlü bir renklendirme algoritması , bazen $2Δ - 1$ kadar çok renk kullanabilir, bu da $gerekenin$ neredeyse iki katı kadar renk olabilir. Ancak, giriş grafiğinin önceden bilinmediği çevrimiçi algoritma ayarında kullanılabilmesi avantajına sahiptir ; bu ayarda, rekabet oranı ikidir ve bu optimaldir: başka hiçbir çevrimiçi algoritma daha iyi bir performans elde edemez. Bununla birlikte, kenarlar rastgele bir sırayla ulaşırsa ve giriş grafiği en azından logaritmik bir dereceye sahipse, daha küçük rekabetçi oranlar elde edilebilir.

Bazı yazarlar , herhangi bir çoklu grafiğin kesirli kromatik indeksinin ( doğrusal programlama kullanılarak polinom zamanında hesaplanabilen bir sayı) kromatik indeksin içinde olduğunu ima eden varsayımlarda bulunmuştur . Bu varsayımlar doğruysa, Vizing'in basit grafikler için teoremi ile bilinenleri eşleştirerek, çoklu grafik durumunda kromatik indeksten asla birden fazla olmayan bir sayı hesaplamak mümkün olacaktır. Genel olarak kanıtlanmamış olsa da, bu varsayımların, yeterince büyük çokluğa sahip çoklu grafikler için olabileceği gibi , kromatik indeks en az olduğunda geçerli olduğu bilinmektedir . $\Delta +{\sqrt {\Delta/2}}$

Kesin algoritmalar

Bir grafiğin bir veya iki renkle kenar renkli olup olmadığını test etmek kolaydır, bu nedenle kenar renklendirmenin ilk önemsiz durumu, bir grafiğin 3 kenarlı renklendirmeye sahip olup olmadığını test etmektir. De (2009) Kowalik gösterdi, bu bir grafiktir, 3-kenar-boyama süresi içinde olup olmadığını test etmek için olası bir $O (1.344 N)$ sadece polinom alan kullanırken,. Bu zaman sınırı üstel olmasına rağmen, renklerin kenarlara olası tüm atamaları üzerinde kaba kuvvet aramasından önemli ölçüde daha hızlıdır. $n$ köşeli her çift bağlantılı 3-düzenli grafiğin $O(2$ $n$ $/2$ $)$ 3-kenar renklendirmesi vardır; bunların tümü zaman içinde listelenebilir $O(2$ $n$ $/2$ $)$ (tek bir renk bulma zamanından biraz daha yavaş); olarak Greg Kuperberg gözlenen bir grafiği prizma aşırı $n$ $/ 2$ taraflı çokgen sahip $Q'dan (2$ $N$ $/ 2$ $)$ bağlanmış, bu sıkı olduğunu gösteren boya maddeleri (yerine üst bağlanmış alt).

Giriş grafiğinin çizgi grafiğine tepe noktası renklendirmesi için kesin algoritmalar uygulayarak , $2$ $m$ $m$ $O(1)$ zamanında ve üstel boşlukta gerekli renk sayısından bağımsız olarak $m$ kenarlı herhangi bir grafiği en uygun şekilde kenar renklendirmek mümkündür. veya zamanında $O(2.2461$ $m$ $)$ ve sadece polinom uzayı ( Björklund, Husfeldt & Koivisto 2009 ).

Kenar renklendirme, üç renk için bile NP-tamamlandığından , renk sayısı ile parametrelendiğinde sabit parametre izlenebilir olması pek olası değildir . Ancak, diğer parametreler için izlenebilir. Özellikle, Zhou, Nakano & Nishizeki (1996) , $w w$ ağaç genişliği grafikleri için , $O($ $nw$ $(6$ $w$ $)$ $w$ $($ $w$ $+ 1)/2$ $)$ zamanında optimal bir kenar renginin hesaplanabileceğini gösterdiler, bu sınır , süper-üssel olarak bağlı bir sınırdır. ilgili $ağırlık$ ancak lineer numarası ile $n$ grafikte köşe.

Nemhauser & Park (1991) , kenar renklendirme problemini bir tamsayı programı olarak formüle eder ve bir tamsayı programlama çözücüsünü kullanarak kenar renk grafiklerini kullanma deneyimlerini tanımlar. Ancak, algoritmalarının herhangi bir karmaşıklık analizini gerçekleştirmediler.

Ek özellikler

Benzersiz 3 renklendirilebilir genelleştirilmiş Petersen grafiği

G (9,2)

. Üç renk sınıfından biri açık kenarlarla gösterilir ve diğer ikisi, açık kenarları her yönde 40° döndürerek veya karanlık Hamilton döngüsünü alternatif kenarlara bölerek bulunabilir.

Bir grafik edilir benzersiz $k$ içine kenarları bölünmesi tek bir yolu varsa -kenar-yalandan $k$ görmezden, renk sınıfları $k!$ renklerin olası permütasyonları. İçin $k \neq 3$ , sadece benzersiz $k$ -kenar-renklendirilebilir grafikler yolları, döngüleri ve vardır yıldızlı ancak için $k = 3$ başka grafikler de benzersiz olabilir $k$ -kenar-renklendirilebilir. Her benzersiz 3 kenarlı renklendirilebilir grafiğin tam olarak üç Hamiltonian döngüsü vardır (üç renk sınıfından birinin silinmesiyle oluşturulur), ancak genelleştirilmiş Petersen grafikleri gibi, üç Hamiltonian döngüsüne sahip olan ve benzersiz olarak 3 renklendirilemeyen 3 düzenli grafikler vardır. $n$ $\geq 2$ için $G (6 n + 3, 2)$ . Bilinen tek düzlemsel olmayan benzersiz 3 renklendirilebilir grafik, genelleştirilmiş Petersen grafiği $G$ $(9,2)$ 'dir ve başka hiçbir şeyin olmadığı varsayılmıştır.

Tam ikili grafik K _3,3 farklı hatlarda paralel çizgi segmentleri olarak çizilen renk sınıfların her biri ile.

Folkman & Fulkerson (1969) , $m 1, m 2, m 3, ...$ sayılarının artmayan dizilerini , birinci rengin $m$ $1$ kenarları ile verilen bir $G$ grafiğinin uygun bir kenar renklendirmesinin olması özelliği ile araştırdı , ikinci rengin $m$ $2$ kenarları, vb. Onlar gözlemlediler ki, eğer bir $P$ dizisi bu anlamda mümkünse ve sözlükbilimsel olarak aynı toplamlı bir $Q$ dizisinden daha büyükse , o zaman $Q'nun$ da mümkün olduğunu gözlemlediler . , Eğer $p$ $>$ $S$ lexicographic amacıyla, daha sonra $p$ transforme edilebilir $Q$ numaralarının bir azaltan her biri bir dizi aşamayı tarafından $m$ $i$ bir birim ve bir sonraki sayısı arttıkça $m$ $j$ ile $i$ $<$ $j$ bir birim . Kenar renklendirmeleri açısından, $P'yi$ gerçekleştiren bir renklendirmeden başlayarak , bu aynı adımların her biri , iki renk arasında değişen maksimum bir kenar yolu olan bir Kempe zincirinde $i$ ve $j$ renkleri değiştirilerek gerçekleştirilebilir . Özellikle, herhangi bir grafiğin eşit kenar renklendirmesi, her iki renk sınıfının boyut olarak en fazla bir birim farklılık gösterdiği optimal sayıda renkle kenar renklendirmesi vardır.

De Bruijn ve-erdos teoremi sonlu grafikler birçok kenar renklendirici özelliklere aktarmak için kullanılabilir sonsuz grafikler . Örneğin, bir grafiğin derecesini kromatik indeksine bağlayan Shannon ve Vizing'in teoremlerinin her ikisi de doğrudan sonsuz grafiklere genelleşir.

Richter (2011) , verilen bir kübik grafiğin grafik çizimini , çizimdeki tüm kenarların üç farklı eğimden birine sahip olduğu ve iki kenarın birbiriyle aynı çizgide olmadığı özellikleriyle bulma problemini ele almaktadır . Böyle bir çizim varsa, o zaman açıkça kenarların eğimleri, grafiğin 3 kenarlı renklendirmesinde renk olarak kullanılabilir. Örneğin, $K$ $3,3$ fayda grafiğinin düzgün bir altıgenin kenarları ve uzun köşegenleri olarak çizilmesi , grafiğin bu şekilde 3 kenarlı bir renklendirmesini temsil eder. Richter'in gösterdiği gibi, belirli bir Tait rengine sahip 3-düzenli basit iki parçalı bir grafik, yalnızca ve ancak grafiğin 3-kenar bağlantılı olması durumunda verilen rengi temsil eden bu tip bir çizime sahiptir . İki parçalı olmayan bir grafik için durum biraz daha karmaşıktır: grafiğin iki parçalı çift kapağı 3 kenara bağlıysa ve herhangi bir tek renkli kenar çifti silindiğinde belirli bir renk çizimle temsil edilebilir. hala iki taraflı olmayan alt grafik. Bu koşulların tümü polinom zamanında kolayca test edilebilir; ancak, 4 kenarlı renkli 4 düzenli bir grafiğin, renkleri eğimlerle temsil eden dört eğimli bir çizime sahip olup olmadığını test etme sorunu , gerçeklerin varoluşsal teorisi için tamamlanmıştır , en az onun kadar zor bir karmaşıklık sınıfıdır. NP-tam olmak.

Gibi bir grafik maksimum derecede ve en uygun sayısı ile ilgili olan gibi, renk indeksi ile yakından ilgilidir doğrusal arboricity $la (G)$ bir grafiktir ve $G$ , doğrusal orman minimum sayıda (yollarının ayrık birlikleri) içine grafiğin kenarları bölümlenmiş olabilir. Eşleştirme özel bir tür doğrusal ormandır ve diğer yönde, herhangi bir doğrusal orman 2 kenarlı olabilir, bu nedenle her $G$ için $la(G) \leq χ'(G) \leq 2 la(G)$ . Akiyama'nın varsayımı ( Jin Akiyama'nın adıyla anılır ) , $2 la($ $G$ $) - 2 \leq χ'($ $G$ $) \leq 2 la($ $G$ $)$ $'den$ daha güçlü bir şekilde çıkacağını belirtir . Maksimum derece üç grafikler için, $la($ $G$ $)$ her zaman tam olarak ikidir, bu durumda $χ'($ $G$ $) \leq 2 la($ $G$ $)$ sınırı Vizing teoremi tarafından verilen sınırla eşleşir. $\mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {\Delta +1}{2}}\sağ\rceil$

Diğer çeşitler

Bir bölüm tam ikili grafik K _4,4 üç orman halinde, bu arboricity üç sahip olduğunu gösteren.

Thue sayısı bir grafik güçlü ihtiyacını karşılamak renklendirme bir kenar gerekli renk sayısı olduğu, her çift uzunluklu yolu, renk yol şekli farklı dizilerin, birinci ve ikinci yarılar.

Bir grafiğin ağaçsılığı , her rengin kenarlarının döngüsü olmaması için gereken minimum renk sayısıdır (standart kenar renklendirme probleminde bitişik kenar çiftlerinin olmaması yerine). Yani, grafiğin kenarlarının bölünebileceği minimum orman sayısıdır . Kromatik indeksin aksine, bir grafiğin ağaçlık özelliği polinom zamanında hesaplanabilir.

Liste kenarı renklendirme , her kenarın bir renk listesiyle ilişkilendirildiği bir grafiğin verildiği ve her kenarın renginin o kenarın listesinden çizildiği uygun bir kenar renklendirmesinin bulunması gereken bir problemdir. $G$ grafiğinin liste kromatik indeksi , kenarlar için renk listelerini nasıl seçerse seçsin, her kenar listesinde en az $k$ renk olduğu sürece , o zaman bir renklendirmenin garanti edildiği özelliğine sahip en küçük $k$ sayısıdır . mümkün olmak. Bu nedenle, liste kromatik indeksi her zaman en az kromatik indeks kadar büyüktür. Dinitz tahmin kısmi tamamlanması üzerine , Latin kareler listesi kenarı renk sayısı ifadesine olarak adlandırılabilecek edilebilir tam ikili grafik $K$ $, n, n$ , kendi kenar renk sayısına eşittir $, n$ . Galvin (1995) , daha genel olarak, her iki parçalı grafikte kromatik indeks ve liste kromatik indeksin eşit olduğunu kanıtlayarak varsayımı çözdü. Kromatik indeks ile liste kromatik indeksi arasındaki eşitliğin, daha genel olarak, kendi kendine döngüleri olmayan keyfi çoklu grafikler için geçerli olduğu varsayılmıştır; bu varsayım açık kalır.

Köşe renklendirmesinin yaygın olarak incelenen diğer birçok varyasyonu da kenar renklendirmelerine genişletildi. Örneğin, tam kenar boyama kenar renklendirme varyantıdır tam boyama , boyama uygun bir kenarı olan renklerin her bir çift bitişik kenarların en azından bir çifti tarafından temsil edilmelidir ve burada hedef renklerin sayısı en üst düzeye çıkarmak . Güçlü kenar renklendirme, bitişik uç noktaları olan her iki kenarın farklı renklere sahip olması gereken bir kenar renklendirme olan güçlü renklendirmenin kenar renklendirme çeşididir . Güçlü kenar renklendirme, kablosuz ağlar için kanal ayırma şemalarında uygulamalara sahiptir .

Asiklik kenar renklendirme, her iki renk sınıfının bir asiklik alt grafiği (yani bir orman) oluşturduğu bir kenar renklendirme olan asiklik renklendirmenin kenar renklendirme çeşididir . Bir grafiğin ile gösterilen asiklik kromatik indeksi, uygun bir asiklik kenar renklendirmesine sahip olmak için gereken en küçük renk sayısıdır . Maksimum derecesinin nerede olduğu tahmin edilmiştir . Şu anda en iyi bilinen sınır . Geniş çevresi olduğunda sorun daha kolay hale gelir . Daha spesifik olarak, çevresi en az ise , o zaman olacak şekilde bir sabit vardır . Benzer bir sonuç için tüm olduğunu bir vardır , eğer bu tür bir çevresi vardır, en az , daha sonra . ${\görüntüleme stili G}$ ${\görüntüleme stili a'(G)}$ ${\görüntüleme stili G}$ $a'(G)\leq \Delta +2$ ${\görüntüleme stili\Delta }$ ${\görüntüleme stili G}$ $a'(G)\leq \lceil 3.74(\Delta -1)\rceil$ ${\görüntüleme stili G}$ ${\görüntüleme stili c}$ ${\görüntüleme stili G}$ $c\Delta \log\Delta$ $a'(G)\leq \Delta +2$ $\epsilon >0$ ${\görüntüleme stili g}$ ${\görüntüleme stili G}$ ${\görüntüleme stili g}$ $a'(G)\leq (1+\epsilon )\Delta$

Eppstein (2013) kübik grafiklerin 3 kenarlı renklendirmelerini, hiçbir iki bikromatik döngünün birbiriyle tek bir kenardan fazlasını paylaşmadığı ek özelliğiyle inceledi. Böyle bir renklendirmenin varlığının, kenarları koordinat eksenlerine paralel ve her eksen paralel çizgisi en fazla iki köşe içeren üç boyutlu bir tamsayı ızgarası üzerinde bir grafik çiziminin varlığına eşdeğer olduğunu gösterdi . Bununla birlikte, standart 3 kenarlı boyama problemi gibi, bu tipte bir renklendirme bulmak da NP-tamamlanmıştır.

Toplam renklendirme , hem köşelerin hem de kenarların renklendirilmesini gerektirerek köşe ve kenar renklendirmeyi birleştiren bir renklendirme şeklidir. Herhangi bir köşe ve kenarın veya bir kenarın ve bir kenarın herhangi bir olay çifti, herhangi iki bitişik köşenin olması gerektiği gibi farklı renklere sahip olmalıdır. Herhangi bir grafiğin, renk sayısının en fazla maksimum derece artı iki olduğu toplam bir renge sahip olduğu varsayılmıştır (Vizing teoremi ve Brooks teoremini birleştirerek ), ancak bu kanıtlanmamıştır.

Bir yüzeydeki 3-düzenli bir grafik 3-kenar renkli ise, ikili grafiği , aynı zamanda kenar renkli olan (genel olarak, düzgün bir şekilde kenar renkli olmasa da) yüzeyin bir üçgenlemesini oluşturur, öyle ki her üçgenin bir tane vardır. her rengin kenarı. Renklerin üçgenlemenin köşelerinde veya yüzlerinde nasıl düzenlendiğine ilişkin diğer yerel kısıtlamalarla birlikte, üçgenlemelerin diğer renklendirmeleri ve yönelimleri, çeşitli geometrik nesne türlerini kodlamak için kullanılabilir. Örneğin, dikdörtgen alt bölümler (dikdörtgensel bir alt bölümün her köşede birleşen üç dikdörtgen ile daha küçük dikdörtgenlere bölünen bölümleri), kombinatoryal olarak bir "düzenli etiketleme", alt bölüme ikili bir üçgenlemenin kenarlarının iki renklenmesi ile tarif edilebilir. her bir tepe noktasına gelen kenarların, her biri içinde renklerin aynı olduğu dört bitişik alt dizi oluşturması kısıtlaması. Bu etiketleme, dikey kenarların bir renge ve yatay kenarların diğer renge sahip olduğu dikdörtgen alt bölümün kendisinin renklendirilmesine yöneliktir. Bir tepe etrafında renkli kenarların görünme sırasına ilişkin benzer yerel kısıtlamalar, düzlemsel grafiklerin düz çizgi ızgara yerleştirmelerini ve eksen paralel kenarları olan üç boyutlu çokyüzlüleri kodlamak için de kullanılabilir. Bu üç tip düzenli etiketlemenin her biri için, sabit bir grafiğin düzenli etiketleme seti , aynı grafiğe dayalı tüm geometrik yapıları hızlı bir şekilde listelemek için kullanılabilen bir dağıtım kafesi oluşturur (aynı iskelete sahip tüm eksen-paralel çokyüzlüler gibi). ) veya ek kısıtlamaları karşılayan yapıları bulmak için.

Bir deterministik FA bir şekilde yorumlanabilir yönlendirilmiş grafik her köşe aynı üzerinden derece sahip olduğu $d$ , ve burada kenarları vardır $d$ aynı kaynak tepe her iki kenar farklı renklere sahip olduğu şekilde -colored. Yol boyama sorunu sorunudur kenar boyama Elde edilen otomat sahip olacağı bir şekilde, muntazam dışarı derece bir çizge eşzamanlama sözcüğü . Trahtman (2009) , yol renklendirme problemini, verilen grafiğin güçlü bir şekilde bağlantılı ve periyodik olmayan her durumda böyle bir renklendirmenin bulunabileceğini kanıtlayarak çözmüştür .

Ramsey'in teoremi , belirli bir boyutta $s$ olan tek renkli tam alt graflar $K$ $s$ oluşturmaktan kaçınmak için büyük bir tam grafiğin $K$ $n$ kenarlarını $k -$ renklendirme sorunuyla ilgilidir . Teoreme göre, bir $R$ $k$ $($ $s$ $)$ sayısı vardır, öyle ki, $n$ $\geq$ $R$ $($ $s$ $) olduğunda$ , böyle bir renklendirme mümkün değildir. Örneğin, $R,$ $2$ $(3) 6 =$ grafik kenarları ise, yani, $K$ $6$ 2-renkli olarak, her zaman bir tek renkli üçgen olacaktır.

Kenar renkli bir grafikteki bir yolun, üzerinde hiçbir renk tekrarlanmıyorsa, bir gökkuşağı yolu olduğu söylenir . Herhangi iki köşe çifti arasında bir gökkuşağı yolu varsa, grafiğin gökkuşağı renginde olduğu söylenir. Renkleri 1 olan bir G grafiğinin kenar renklendirmesi. . t, tüm renkler kullanılıyorsa renklendirme aralığıdır ve G'nin her bir köşesine gelen kenarların renkleri farklıdır ve bir tamsayı aralığı oluşturur.

Uygulamalar

Komple grafiklerin kenar renklendirmeleri, bir round-robin turnuvasını mümkün olduğunca az raund olarak planlamak için kullanılabilir, böylece her bir yarışmacı çifti rauntlardan birinde birbirleriyle oynar; Bu uygulamada grafiğin köşeleri turnuvadaki yarışmacılara, kenarlar oyunlara, kenar renkleri ise oyunların oynandığı turlara karşılık gelir. Benzer renklendirme teknikleri aynı zamanda her şeyi oynatmayan diğer spor eşleşmelerini planlamak için de kullanılabilir; Örneğin, Ulusal Futbol Ligi'nde , takımların bir önceki yıla ait kayıtlarına göre belirli bir yılda birbirleriyle oynayacak takım çiftleri belirlenir ve daha sonra elde edilen grafiğe kenar renklendirme algoritması uygulanır. Oyunları oynandıkları hafta sonlarına atamak için eşleştirme seti. Bu uygulama için, Vizing'in teoremi, hangi eşleşmeler seçilirse seçilsin (hiçbir takım aynı sezonda iki kez oynamadığı sürece), mevcut haftadan en fazla bir hafta sonu kullanan bir program bulmanın her zaman mümkün olduğunu ima eder. takım başına oyunlar.

Açık çizelgeleme bir sorundur zamanlama üretim süreçleri , burada imal edilecek nesneler bir küme de vardır, her bir nesne (herhangi bir sırada) üzerinde yapılması gereken görevler kümesi vardır ve her bir işlem için bir spesifik gerçekleştirilmelidir aynı makinenin aynı anda yapılmasını gerektiren diğer görevlerin önlenmesi. Eğer tüm görevler aynı uzunluğa sahipse, bu problem iki parçalı bir çoklu grafiğin kenar renklendirmesinden biri olarak formüle edilebilir; burada iki parçalı bölümün bir tarafındaki köşeler üretilecek nesneleri temsil eder, ikili bölümün diğer tarafındaki köşeler ise iki parçalı çoklu grafiği temsil eder. imalat makineleri, kenarlar yapılması gereken görevleri ve renkler her bir görevin gerçekleştirilebileceği zaman adımlarını temsil eder. İki parçalı kenar renklendirme polinom zamanında gerçekleştirilebildiğinden, aynı durum bu kısıtlı açık atölye planlaması durumu için de geçerlidir.

Gandham, Dawande & Prakash (2005) , kenar renklendirmenin bir çeşidi olarak sensör ağlarında zaman bölmeli çoklu erişim ağı iletişim protokolleri için bağlantı zamanlaması problemini inceler . Bu problemde, bir kablosuz iletişim ağının kenarları için zaman aralıkları seçilmelidir, böylece ağın her bir düğümü, her bir komşu düğüm ile girişim olmaksızın iletişim kurabilir. Güçlü bir kenar renklendirme kullanmak (ve her kenar rengi için iki zaman dilimi kullanmak, her yön için bir tane olmak üzere) sorunu çözebilir ancak gereğinden fazla zaman dilimi kullanabilir. Bunun yerine, her biri yönlendirilmiş kenar bu özelliği ile, her bir ağ yönsüz kenar katlama ile oluşturulan yönlendirilmiş grafiğinin bir boyama aramak $UV$ çıkmaya kenarlarından başka bir renkte olan $, v$ ve komşularından $v$ . Bu problem için, $(Δ + 1)$ -kenar boyama için dağıtılmış bir algoritmaya ve birbirleriyle etkileşime girebilecek kenarları yeniden programlayan bir son işleme aşamasına dayanan bir buluşsal yöntem önerirler .

Olarak fiber optik bağlantı , boyama yolu sorunu kısıtlama, her çift için bir fiber optik iletişim ağı üzerinden birbirleri ile iletişim kurmak isteyen düğüm çifti ve yollara renkler konusu (ışık frekanslarını) atama sorun bir fiber segmentini paylaşan iki yol, birbiriyle aynı frekansı kullanmaz. Aynı iletişim anahtarından geçen ancak herhangi bir fiber segmentinden geçmeyen yolların aynı frekansı kullanmasına izin verilir. İletişim ağı, düğümlerin her birine ayrı fiberlerle bağlanan tek bir merkezi anahtarla bir yıldız ağı olarak düzenlendiğinde , yol renklendirme problemi tam olarak bir grafiğin veya çoklu grafiğin kenar renklendirme problemi olarak modellenebilir; grafik köşelerini, iletişim kurmak isteyen düğüm çiftlerini grafik kenarlarını oluşturur ve her bir çift için kullanılabilecek frekanslar kenar renklendirme probleminin renklerini oluşturur. Daha genel bir ağaç topolojisine sahip iletişim ağları için, ağdaki her bir anahtar tarafından tanımlanan yıldız ağları için yerel yol renklendirme çözümleri, tek bir küresel çözüm oluşturmak üzere bir araya getirilebilir.

Açık sorunlar

Jensen ve Toft (1995) kenar renklendirme ile ilgili 23 açık problemi listeler. İçerirler:

Goldberg'in (1973) kromatik indeks ve kesirli indeksin birbirinin içinde olduğu varsayımı, bu, kromatik indeksin polinom zamanında bir renk içinde yaklaşık olmasına izin verir.
Jakobsen ve diğerlerinin, kenar renklendirme için kritik grafiklerin yapısı, herhangi bir alt grafiğin daha küçük maksimum dereceye sahip olduğu veya sınıf 1 olduğu 2. sınıf grafikler hakkında birkaç varsayımı. bu sonunda çürütüldü. Bunu zayıflatan veya kritik grafiklerin ve kritik çoklu grafiklerin köşe sayılarını sınırlayan diğer birkaç varsayım açık kalır.
Vizing'in 2. sınıf düzlemsel grafikler için mümkün olan maksimum dereceleri sınıflandırma problemi.
Fazla dolu subgraph varsayım en azından derecesine sahip grafikler belirten AJW Hilton, $n / 3$ ya da sınıf 1 ya da aynı derecede bir alt grafiğini içeren $Ô$ orijinal grafik olarak ve bir tek sayı olan $k$ bu sayı olduğu köşe bölgesinin alt grafikteki kenarların sayısı $Δ(k - 1)/2'den$ büyüktür ve Herbert Grötzsch ve Paul Seymour'un yüksek dereceli grafikler yerine düzlemsel grafiklerle ilgili benzer bir varsayımı .
Amanda Chetwynd ve Anthony Hilton'un (muhtemelen daha önce Gabriel Andrew Dirac'ın çalışmasına geri dönersek ) bir çift sayıda $n$ köşeli ve en az $n /2$ dereceli düzenli grafiklerin 1. sınıf olduğu varsayımı .
Bir tahmin Claude Berge ve DR Fulkerson 6-normal multigraphs kenar renkli altı renk olabilir köprüsüz bir 3-normal basit grafik her kenar katlama ile oluşturulan bu.
Her bu Fiorini ve Wilson bir varsayım üçgen içermeyen başka düzlemsel grafik, pençe K _1,3 değil, benzersiz 3-kenar-renklendirilebilir .
Her 2012 varsayım ki eğer $G$ bir $d$ -Normal düzlemsel ufak matbaa ardından $G$ isimli $d$ -kenar-renklendirilebilir, ancak ve ancak $G,$ tuhaf olduğu $d$ -kenar bağlı. Bu varsayım, $d$ =3'te ortaya çıkan dört renk teoreminin bir genellemesidir . Maria Chudnovsky , Katherine Edwards ve Paul Seymour , 8 düzenli bir düzlemsel çoklu grafiğin kenar kromatik sayısının 8 olduğunu kanıtladı.

Notlar

Referanslar

Akiyama, Jin; Exoo, Geoffrey; Harary, Frank (1980), "Grafiklerde kaplama ve paketleme. III. Döngüsel ve çevrimsiz değişmezler", Mathematica Slovak , 30 (4): 405–417, MR 0595302.
Alon, Noga (2003), "Kenar renklendirme ikili multigraflar için basit bir algoritma", Information Processing Letters , 85 (6): 301–302 , doi : 10.1016/S0020-0190(02)00446-5 , MR 1956451.
Alon, Noga ; Sudakov, Benny; Zaks, Ayal (2001), "Grafiklerin asiklik kenar renklendirmeleri", Journal of Graph Theory , 37 (3): 157–167, doi : 10.1002/jgt.1010 , MR 1837021.
Andersen, Lars Døvling (1977), "Grafiklerin kenar renklendirmeleri üzerine", Mathematica Scandinavica , 40 (2): 161–175, doi : 10.7146/math.scand.a-11685 , MR 0465922. Chen, Yu & Zang (2011) tarafından alıntılandığı gibi .
Appel, K .; Haken, W. (1976), "Her düzlemsel harita dört renklenebilir", Amerikan Matematik Derneği Bülteni , 82 (5): 711–712, doi : 10.1090/S0002-9904-1976-14122-5 , MR 0424602.
Bahman, Bahman; Mehta, Aranyak; Motwani, Rajeev (2010), "Rastgele sipariş varış modelinde 1.43-rekabetçi çevrimiçi grafik kenarı renklendirme algoritması", Ayrık Algoritmalar Üzerine Yirmi Birinci Yıllık ACM-SIAM Sempozyumu (SODA '10) , s..
Bar-Noy, Amotz; Motwani, Rajeev ; Naor, Joseph (1992), "On-line kenar renklendirme için açgözlü algoritma optimaldir", Information Processing Letters , 44 (5): 251–253, doi : 10.1016/0020-0190(92)90209-E.
Barrett, CL; Istrat, G.; Kumar, VSA; Marathe, MV; Thite, S.; Thulasidasan, S. (2006), "Kablosuz radyo ağlarında kanal ataması için güçlü kenar renklendirme", Proc. Dördüncü Yıllık IEEE Uluslararası Yaygın Bilgi İşlem ve İletişim Çalıştayları Konferansı (PerCom Çalıştayları 2006) , s. 106, doi : 10.1109/PERCOMW.2006.129 , ISBN 0-7695-2520-2, S2CID 5797236.
Biggs, Norman (1972), Guy, Richard K. (ed.), "Bir kenar boyama problemi", Research Problems, American Mathematical Monthly , 79 (9): 1018–1020, doi : 10.2307/2318076 , JSTOR 2318076.
Biggs, Norman (1979), "Bazı tuhaf grafik teorisi", İkinci Uluslararası Kombinatoryal Matematik Konferansı, Annals of the New York Academy of Sciences , 319 (1): 71–81, Bibcode : 1979NYASA.319...71B , doi : 10.1111/j.1749-6632.1979.tb32775.x , S2CID 84995087.
Björklund, Andreas; Husfeldt, Thore; Koivisto, Mikko (2009), "İçerme-dışlama yoluyla bölümlemeyi ayarla" (PDF) , SIAM Journal on Computing , 39 (2): 546–563, doi : 10.1137/070683933 , MR 2529771.
Bosák, Juraj (1972), "Sonlu ve sonsuz grafiklerin kromatik indeksi", Çekoslovak Matematik Dergisi , 22 (97): 272–290, doi : 10.21136/CMJ.1972.101098 , MR 0309777.
Bosak, Juraj; Nešetřil, Jaroslav (1976), "Bir grafiğin tam ve sahte renklendirmeleri", Matematicky Časopis Slovenskej Akadémie Vied , 26 (3): 171–184, MR 0439672.
Cai, XS; Perarnau, G.; Kamış, BA ; Watts, AB (2014), "Geniş çevreli grafiklerin asiklik kenar renklendirmeleri", Rastgele Yapılar ve Algoritmalar , 50 (4): 511–533, arXiv : 1411.3047 , doi : 10.1002/rsa.20695 , S2CID 7727097.
Burke, E.; De Werra, D.; Kingston, J. (2004), "5.6.5 Spor Zaman Çizelgeleme" , JL, Gross; Yellen, J. (eds.), Handbook of Graph Theory , CRC Press, s. 462, ISBN 978-1-58488-090-5.
Chen, Guantao; Yu, Xingxing; Zang, Wenan (2011), " Multigrafların kromatik indeksinin yaklaştırılması ", Journal of Combinatory Optimization , 21 (2): 219–246, doi : 10.1007/s10878-009-9232-y , MR 2770056 , S2CID 169162.
Chudnovsky, Maria ; Edwards, Katherine; Seymour, Paul (2012), "Kenar boyama sekiz düzgün düzlemsel grafikler", arXiv : 1209.1176 [ cs.DM ].
Cole, Richard; Hopcroft, John (1982), " Kenarda renklendirme ikili grafikler", SIAM Journal on Computing , 11 (3): 540–546, doi : 10.1137/0211043 , hdl : 1813/6283 , MR 0664720.
Cole, Richard; Kowalik, Łukasz (2008), "Kenar renklendirme düzlemsel grafikler için yeni doğrusal zaman algoritmaları", Algorithmica , 50 (3): 351–368, doi : 10.1007/s00453-007-9044-3 , MR 2366985 , S2CID 7692895.
Cole, Richard; Ost, Kirstin; Schirra, Stefan (2001), " $O(E log D)$ zamanında kenar renklendirme iki parçalı multigraflar ", Combinatorica , 21 (1): 5–12, doi : 10.1007/s004930170002 , MR 1805711 , S2CID 522145.
Cranston, Daniel W. (2006), "22 renk kullanarak maksimum derece 4 ile grafiklerin güçlü kenar renklendirmesi", Discrete Mathematics , 306 (21): 2772–2778, arXiv : math/0601623 , Bibcode : 2006math.... ..1623C , doi : 10.1016/j.disc.2006.03.053 , MR 2264374 , S2CID 1097275.
Eppstein, David (2013), "Bükümsüz Üç Boyutlu Ortogonal Grafik Çiziminin Karmaşıklığı", Grafik Algoritmaları ve Uygulamaları Dergisi , 17 (1): 35–55, arXiv : 0709.4087 , doi : 10.7155/jgaa.00283 , S2CID 2716392.
Eppstein, David (2010), "Düzenli etiketleme ve geometrik yapılar", Proc. 22. Kanada Hesaplamalı Geometri Konferansı (CCCG 2010) (PDF) , Manitoba Üniversitesi, arXiv : 1007.0221 , Bibcode : 2010arXiv1007.0221E.
Erdös, Paul ; Wilson, Robin J. (1977), "Neredeyse tüm grafiklerin kromatik indeksi üzerine not" (PDF) , Journal of Combinatory Theory , Series B, 23 (2-3): 255-257, doi : 10.1016/0095-8956 (77)90039-9.
Erlebach, Thomas; Jansen, Klaus (2001), "Yol renklendirme ve çağrı planlamanın karmaşıklığı", Teorik Bilgisayar Bilimi , 255 (1–2): 33–50 , doi : 10.1016/S0304-3975(99)00152-8 , MR 1819065.
Ferber, Asaf; Jain, Vishesh (2018), " Psödorastgele grafiklerin 1-faktörleştirmeleri", arXiv : 1803.10361 [ math.CO ].
Fiamčik, J. (1978), "Bir grafiğin asiklik kromatik sınıfı", Math. Slovakya , 28 : 139–145.
Fiorini, S.; Wilson, Robin James (1977), Grafiklerin kenar renklendirmeleri , Matematikte Araştırma Notları, 16 , Londra: Pitman, ISBN 0-273-01129-4, MR 0543798.
Halkçı, Jon ; Fulkerson, DR (1969), "İkili grafiklerde kenar renklendirmeleri", Kombinatoryal Matematik ve Uygulamaları (Proc. Conf., Univ. North Carolina, Chapel Hill, NC, 1967) , Chapel Hill, NC: Univ. North Carolina Press, s. 561–577, MR 0262112.
Fouquet, J.-L.; Jolivet, J.-L. (1983), "Grafiklerin güçlü kenar renklendirmeleri ve çoklu $k-$ gonlara uygulamalar ", Ars Combinatoria , 16 (A): 141–150, MR 0737086.
Friz, Alan M. ; Kriveleviç, Michael; Sudakov, Benny (2005), "Rastgele grafiklerin güçlü kromatik indeksi" (PDF) , SIAM Journal on Discrete Mathematics , 19 (3): 719–727 (elektronik), doi : 10.1137/S0895480104445757 , MR 2191290.
Gabow, Harold N. (1976), "Using Euler partition to edge color bipartite multigraphs", International Journal of Computer and Information Sciences , 5 (4): 345–355, doi : 10.1007/BF00998632 , MR 0422081 , S2CID 36331285.
Gabow, Harold N .; Nishizeki, Takao ; Kariv, Oded; Leven, Daniel; Terada, Osamu (1985), Kenar boyama grafikleri için algoritmalar , Tech. Rapor TRECIS-8501, Tohoku Üniversitesi.
Gabow, Harold N .; Westermann, Herbert H. (1992), "Ormanlar, çerçeveler ve oyunlar: matroid toplamları ve uygulamaları için algoritmalar", Algorithmica , 7 (5–6): 465–497, doi : 10.1007/BF01758774 , MR 1154585 , S2CID 40358357.
Galvin, F. (1995), " Bipartite multigraph'ın liste kromatik indeksi", Journal of Combinatory Theory , Series B, 63 (1): 153–158, doi : 10.1006/jctb.1995.1011.
Gandham, S.; Dawande, M.; Prakash, R. (2005), "Sensör ağlarında bağlantı çizelgeleme: dağıtılmış kenar renklendirmesi yeniden ziyaret edildi", Proc. 24th INFOCOM , 4 , s. 2492–2501, doi : 10.1109/INFCOM.2005.1498534 , ISBN 0-7803-8968-9, S2CID 8085139.
Giotis, İ.; Kirousis, L.; Psaromiligkos, KI; Thilikos, DM (2015), "Algoritmik Lovász Local Lemma ve asiklik kenar renklendirme üzerine", Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) , s. 16, doi : 10.1137/1.9781611973761.2 , ISBN 978-1-61197-376-1.
Goldberg, MK (1973), "Neredeyse maksimum olan bir kromatik indekse sahip çoklu grafikler ", Diskret. analiz. (23): 3–7, 72, MR 0354429. Chen, Yu & Zang (2011) tarafından alıntılandığı gibi .
Habib, M.; Péroche, B. (1982), "Lineer arboricity hakkında bazı problemler", Discrete Mathematics , 41 (2): 219–220, doi : 10.1016/0012-365X(82)90209-6 , MR 0676882.
Holyer, Ian (1981), "Kenar boyamanın NP bütünlüğü", SIAM Journal on Computing , 10 (4): 718–720, doi : 10.1137/0210055.
Horak, Peter; Niepel, Ľudovít (1982), "Kübik grafikler için doğrusal bir ağaçlık teoreminin kısa bir kanıtı", Acta Mathematica Universitatis Comenianae , 40/41: 275–277, MR 0686983.
Jensen, Tommy R.; Toft, Bjarne (1995), Grafik Renklendirme Problemleri , New York: Wiley-Interscience, ISBN 0-471-02865-7.
Karloff, Howard J.; Shmoys, David B. (1987), "Kenar renklendirme problemleri için verimli paralel algoritmalar", Journal of Algorithms , 8 (1): 39–52, doi : 10.1016/0196-6774(87)90026-5 , MR 0875324.
Konig, D. (1916), "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre" , Mathematische Annalen , 77 (4): 453-465, doi : 10.1007 / BF01456961 , hdl : / 127.635 10338.dmlcz , S2CID 121097364 , arşivlenen dan orijinal 2015-01-19 tarihinde , alınan 2013-09-30.
Kowalik, Łukasz (2009), "Üç renkle iyileştirilmiş kenar renklendirme", Teorik Bilgisayar Bilimi , 410 (38–40): 3733–3742, doi : 10.1016/j.tcs.2009.05.005 , MR 2553326.
Mahdian, Mohammad (2002), "Güçlü kenar renklendirmenin hesaplama karmaşıklığı üzerine", Discrete Applied Mathematics , 118 (3): 239–248, doi : 10.1016/S0166-218X(01)00237-2 , MR 1892971.
Meredith, Guy HJ; Lloyd, E. Keith (1973), "The Footballers of Croam", Journal of Kombinatory Theory , Seri B, 15 (2): 161–166, doi : 10.1016/0095-8956(73)90016-6.
Mısra, J.; Gries, David (1992), "Vizing Teoreminin yapıcı bir kanıtı", Bilgi İşlem Mektupları , 41 (3): 131–133, doi : 10.1016/0020-0190(92)90041-S.
Muthu, Rahul; Narayanan, N.; Subramanian, CR (2007), " Çevrimsiz kenar renklendirmede iyileştirilmiş sınırlar", Discrete Mathematics , 307 (23): 3063–3069, doi : 10.1016/j.disc.2007.03.006 , MR 2371078.
Nash-Williams, C. St. JA (1964), "Sonlu grafiklerin ormanlara ayrıştırılması", Journal of the London Mathematical Society , Second Series, 39 : 12, doi : 10.1112/jlms/s1-39.1.12 , MR 0161333
Nemhauser, George L .; Park, Sungsoo (1991), "Kenar renklendirmeye çokyüzlü bir yaklaşım", Yöneylem Araştırma Mektupları , 10 (6): 315–322, doi : 10.1016/0167-6377(91)90003-8 , MR 1128970.
Richter, David A. (2011), Brandes, Ulrik'te "Tait ile renklendirilebilir bir grafik nasıl çizilir" ; Cornelsen, Sabine (ed.), Proc. 18. Uluslararası Grafik Çizimi Sempozyumu (GD 2010) , Bilgisayar Bilimlerinde Ders Notları, 6502 , Springer-Verlag, s. 353–364, doi : 10.1007/978-3-642-18469-7_32 , ISBN 978-3-642-18468-0.
Sanders, Daniel P. ; Zhao, Yue (2001), "Maksimum derece yedi olan düzlemsel grafikler sınıf I'dir ", Journal of Combinatory Theory , Series B, 83 (2): 201–212, doi : 10.1006/jctb.2001.2047.
Seymour, PD (1979), "Kübik grafikler ve Fulkerson ve Tutte varsayımları üzerine", Londra Matematik Derneği Bildirileri , Üçüncü Seri, 38 (3): 423–460, doi : 10.1112/plms/s3-38.3 .423 , MR 0532981.
Schwenk, Allen J. (1989), "Belirli genelleştirilmiş Petersen grafiklerinde Hamilton döngülerinin sayımı", Journal of Combinatory Theory , Series B, 47 (1): 53–59, doi : 10.1016/0095-8956(89)90064- 6 , MR 1007713.
Shannon, Claude E. (1949), "Bir ağın çizgilerini renklendirme üzerine bir teorem", J. Math. Fizik , 28 (1–4): 148–151, doi : 10.1002/sapm1949281148 , hdl : 10338.dmlcz/101098 , MR 0030203.
Skiena, Steven S. (2008), "16.8 Kenar Boyama", Algoritma Tasarım Kılavuzu (2. baskı), Springer-Verlag, pp. 548–550, doi : 10.1007/978-1-84800-070-4_16 , ISBN 978-1-84800-069-8. Stony Brook Algorithm Repository'deki kitabın bu bölümü için web sitesine de bakın .
Soifer, Alexander (2008), Matematiksel Boyama Kitabı , Springer-Verlag, ISBN 978-0-387-74640-1.
Tait, PG (1880), "Haritaların renklendirilmesine ilişkin açıklamalar", Proc. R. Soc. Edinburgh , 10 : 729, doi : 10.1017/S0370164600044643.
Trahtman, Avraham N. (2009), "Yol boyama problemi", Israel Journal of Mathematics , 172 (1): 51–60, arXiv : 0709.0099 , doi : 10.1007/s11856-009-0062-5 , S2CID 515742.
Vizing, VG (1964), " P- grafının kromatik sınıfının bir tahmini üzerine ", Diskret. analiz. , 3 : 25–30, MR 0180505.
Vizing, VG (1965), "Belirli kromatik sınıfa sahip kritik grafikler", Metody Diskret. analiz. , 5 : 9–17. (Rusça.)
Williamson, DP ; Salon, Los Angeles; Hoogeveen, JA; Hurkens, CAJ; Lenstra, JK ; Sevast'janov, SV; Shmoys, DB (1997), "Kısa mağaza programları", Yöneylem Araştırması , 45 (2): 288–294, doi : 10.1287/opre.45.2.288 , JSTOR 171745 , MR 1644998.
Zhou, Xiao; Nakano, Shin-ichi; Nishizeki, Takao (1996), "Kenar boyama kısmi $k$ -ağaçlar", Journal of Algorithms , 21 (3): 598–617, doi : 10.1006/jagm.1996.0061 , MR 1417666.

Languages

In other projects