Gyárfás–Sumner-sejtés

A matematika megoldatlan problémája:
Az egy adott fát és egy adott klikket feszített részgráfként nem tartalmazó gráfok kromatikus száma korlátos-e?
(A matematika további megoldatlan problémái)

A matematika, azon belül a gráfelmélet területén a Gyárfás–Sumner-sejtés azt állítja, hogy tetszőleges fát és teljes gráfot választva, a feszített részgráfként sem -t, sem -t nem tartalmazó gráfok konstans számú színnel jól színezhetők. Ezzel ekvivalens megfogalmazás szerint, a - és -mentes gráfok -korlátosak.[1] A sejtés nevét Gyárfás Andrásról és David Sumnerről kapta, akik egymástól függetlenül 1975-ben, illetve 1981-ben megfogalmazták.[2][3] Jelenleg bizonyítatlan.[4]

A sejtésben nem lehetséges -t kört tartalmazó gráfra cserélni. Ahogy Erdős Pál és Hajnal András megmutatták, léteznek tetszőlegesen magas kromatikus számú, ugyanakkor tetszőlegesen nagy girthű háromszögmentes gráfok.[5] Ezen gráfok felhasználásával előállíthatók olyan gráfok, amik elkerülnek bármely fixen választott, kört tartalmazó gráfot és (2 csúcsnál nagyobb) klikket feszített részgráfként, de tetszőlegesen választott értéknél magasabb a kromatikus számuk.[1]

A sejtést bizonyították néhány speciálisan megválasztott -re, így útgráfokra,[6] csillagokra és kettő sugarú fákra.[7] Ismert az is, hogy azok a gráfok, melyek nem tartalmaznak bármely konkrét fát felosztásként, -korlátosak.[1]

Fordítás

  • Ez a szócikk részben vagy egészben a Gyárfás–Sumner conjecture című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

  1. ↑ a b c Scott, A. D. (1997), "Induced trees in graphs of large chromatic number", Journal of Graph Theory 24 (4): 297–311, DOI 10.1002/(SICI)1097-0118(199704)24:4<297::AID-JGT2>3.3.CO;2-X
  2. ↑ Gyárfás, A. (1975), "On Ramsey covering-numbers", Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, vol. 10, Colloq. Math. Soc. János Bolyai, Amsterdam: North-Holland, pp. 801–816
  3. ↑ Sumner, D. P. (1981), "Subtrees of a graph and the chromatic number", The theory and applications of graphs (Kalamazoo, Mich., 1980), Wiley, New York, pp. 557–576
  4. ↑ Chudnovsky, Maria & Seymour, Paul (2014), "Extending the Gyárfás-Sumner conjecture", Journal of Combinatorial Theory, Series B 105: 11–16, DOI 10.1016/j.jctb.2013.11.002
  5. ↑ Erdős, P. & Hajnal, A. (1966), "On chromatic number of graphs and set-systems", Acta Mathematica Academiae Scientiarum Hungaricae 17: 61–99, doi:10.1007/BF02020444, <https://users.renyi.hu/~p_erdos/1966-07.pdf>
  6. ↑ Gyárfás, A. (1987), "Problems from the world surrounding perfect graphs", Zastosowania Matematyki 19 (3-4): 413–441 (1988)
  7. ↑ Kierstead, H. A. & Penrice, S. G. (1994), "Radius two trees specify χ-bounded classes", Journal of Graph Theory 18 (2): 119–129, DOI 10.1002/jgt.3190180203

További információk

Read other articles:

Hwang Hee-chan

Dalam nama Korean ini, nama keluarganya adalah Hwang. Hwang Hee-chan Hwang bermain untuk Red Bull Salzburg pada 2017Informasi pribadiNama lengkap Hwang Hee-chan[1]Tanggal lahir 26 Januari 1996 (umur 28)[2]Tempat lahir Chuncheon, Korea SelatanTinggi 177 cm (5 ft 10 in)[2]Posisi bermain PenyerangInformasi klubKlub saat ini Wolverhampton WanderersNomor 11Karier junior2009–2012 Pohang Jecheol Middle School2012–2015 Pohang Jecheol High SchoolKarier s...

 

Noble snipe

Species of bird Noble snipe Conservation status Near Threatened  (IUCN 3.1)[1] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Aves Order: Charadriiformes Family: Scolopacidae Genus: Gallinago Species: G. nobilis Binomial name Gallinago nobilisSclater, PL, 1856 The noble snipe (Gallinago nobilis) is a small stocky wader. It breeds in the Andes of Colombia, Ecuador, Peru and Venezuela above or just below the treeline. It is entirely seden...

 

St. Mary's Church (Staten Island)

Building in New York City, United States of AmericaThe Church of St. MarySt. Mary's R. C. Church Rosebank, Staten Island, N.YGeneral informationTown or cityRosebank, Staten Island, New York CityCountryUnited States of AmericaClientRoman Catholic Archdiocese of New York The Church of St. Mary is a Roman Catholic parish church in the Roman Catholic Archdiocese of New York, located at 1101 Bay Street, Staten Island, New York City. St. Mary's is the second oldest of the 36 Roman Catholic parishes...

Ardon (rivière)

Pour les articles homonymes, voir Ardon. L'Ardon Source de l'Ardon à Laon rue des Bains avec le lavoir. Cours de l’Ardon l'Ardon sur OpenStreetMap. Caractéristiques Longueur 11,2 km [1] Bassin 134 km2 [2] Bassin collecteur la Seine Débit moyen 1,72 m3/s (Chaillevois) [2] Nombre de Strahler 4 Organisme gestionnaire Syndicat intercommunal de gestion de l'Ardon et de la moyenne Ailette Régime pluvial océanique Cours Source source · Localisation Laon · Altitude 68 m ...

 

Stanisław Samostrzelnik

Questa voce sugli argomenti religiosi polacchi e pittori polacchi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Stanisław Samostrzelnik detto anche Stanisław z Krakowa o Stanisław z Mogiły (circa 1490 – Mogiła (Cracovia), 1541) è stato un pittore e monaco cristiano polacco del Rinascimento. Illustrazione del Liber geneseos illustris familiae Schidloviciae del 1532, con il possibile autoritratto dell'autore come giullare Appartenente all'ordi...

 

Jaws

Artikel ini sudah memiliki daftar referensi, bacaan terkait, atau pranala luar, tetapi sumbernya belum jelas karena belum menyertakan kutipan pada kalimat. Mohon tingkatkan kualitas artikel ini dengan memasukkan rujukan yang lebih mendetail bila perlu. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) JawsPosterSutradaraSteven SpielbergProduserDavid Brown Richard D. ZanuckSkenarioPeter BenchleyCarl GottliebBerdasarkanNovel:Peter BenchleyPemeranRoy ScheiderRobert ShawRichard ...

WBNB-TV

Television station in the U.S. Virgin Islands (1961–1989) WBNB-TVCharlotte Amalie, U.S. Virgin IslandsChannelsAnalog: 10 (VHF)ProgrammingAffiliationsCBS (1961–1989)NBC (secondary, 1961–1983)NET (secondary, 1961–1970)OwnershipOwnersee § OwnershipHistoryFounded1960 (1960)First air dateJuly 22, 1961 (1961-07-22)Last air dateSeptember 17, 1989 (1989-09-17)(28 years, 57 days)Call sign meaningBob and Bob (Bob Noble and Bob Moss, station co-...

 

Maddalena di Valois (1443-1495)

Maddalena di Francia insieme al suo promesso sposo, Ladislao il Postumo Re di Francia - CapetingiValois Filippo VI (1328-1350) Figli Giovanni II Filippo Giovanni II (1350-1364) Figli Carlo V Luigi Giovanni Giovanna Maria Filippo Isabella Carlo V (1364-1380) Figli Carlo VI Luigi Caterina Carlo VI (1380-1422) Figli Isabella Giovanna Maria Michela Luigi Giovanni Caterina Carlo VII Carlo VII (1422-1461) Figli Luigi XI Caterina Iolanda Giovanna Maddalena Carlo Luigi XI (1461-1483) Figli Anna Giova...

 

Annie Glenn

American advocate (1920–2020) Annie GlennGlenn in 1965BornAnna Margaret Castor(1920-02-17)February 17, 1920Columbus, Ohio, U.S.DiedMay 19, 2020(2020-05-19) (aged 100)Saint Paul, Minnesota, U.S.Resting placeArlington National CemeteryArlington, VirginiaAlma materMuskingum UniversityOccupation(s)Disabilities advocate, philanthropistSpouse John Glenn ​ ​(m. 1943; died 2016)​Children2 Anna Margaret Glenn (née Castor; February 17, 1920&#...

قائمة المنظمات البيئية

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016) هذه هي قائمة بالمنظمات البيئية. المقالة الرئيسة: منظمة بيئية واقرأ أيضا: قائمة منظات حماية البيئة (List of conserva...

 

Jack Smith and the Destruction of Atlantis

2006 American filmJack Smith and the Destruction of AtlantisDirected byMary JordanWritten byMary JordanProduced byMary JordanKenneth Wayne PeraltaStarringJohn WatersMary Sue SlaterRichard ForemanMario MontezGary IndianaJonas MekasSylvère LotringerThomas Lanigan-SchmidtUzi ParnesJohn ZornDistributed byTongue PressMonk MediaRelease dates April 26, 2006 (2006-04-26) (Tribeca Film Festival) April 11, 2007 (2007-04-11) (United States) Running time94 minutesCo...

 

Zinco

Disambiguazione – Se stai cercando la casa editrice spagnola, vedi Ediciones Zinco. Zinco     30 Zn                                                                                                              ...

List of One Tree Hill characters

Five of the original main cast members: top row (L-R) Murray, Burton and Lenz; bottom row (L-R) Bush and Lafferty One Tree Hill is an American television series created by Mark Schwahn for The WB in 2003. After Season 3, The WB and UPN merged to form The CW, which then became the broadcaster for the show in the United States. Schwahn served as executive producer while also writing and directing for the show, including the premieres and finales of all seasons. The show began with nine main ch...

 

سلطة بلانكيت

جزء من سلسلة مقالات حولالمطبخ العربي حسب البلد الجزيرة العربية البحرين الإمارات الكويت سلطنة عمان قطر السعودية اليمن المغرب الكبير الجزائر ليبيا موريتانيا المغرب تونس الشام العراق الأردن لبنان فلسطين سوريا نهر النيل مصر السودان القرن الأفريقي جيبوتي الصومال المحيط اله�...

 

الدوري التونسي لكرة اليد 1996–97

الدوري التونسي لكرة اليد للرجال الموسم 1996-1997 البلد تونس  المنظم الجامعة التونسية لكرة اليد  النسخة 42 عدد الفرق 12   الفائز الترجي الرياضي التونسي الدوري التونسي لكرة اليد 1995–96  الدوري التونسي لكرة اليد 1997–98  تعديل مصدري - تعديل   الدوري التونسي لكرة اليد 1996-19...

阿尔察赫省

此條目没有列出任何参考或来源。 (2020年10月28日)維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。 阿爾察赫Արցախ亞美尼亞王國的省前189年—387年阿爾察赫省（綠）在阿美尼亞的位置坐标：40°04′N 46°56′E / 40.07°N 46.93°E / 40.07; 46.93首府Parnes歷史歷史時期古典时代、中世纪• �...

 

Michiko Maeda

Japanese actress Michiko MaedaMichiko Maeda in a movie posterBorn (1934-02-27) February 27, 1934 (age 90)[1]Osaka, Japan Michiko Maeda (前田通子, Maeda Michiko) is a Japanese film and television actress who became known as the first Japanese actress to appear in a nude scene in a mainstream film. Life and career Michiko Maeda was born in Osaka Prefecture on February 27, 1934. She was working in a department store in the Nihonbashi district of Tokyo when she began working as a...

 

Bryan Woodward

American middle-distance runner Bryan Woodward (born August 3, 1974) is an American former middle distance runner who competed in the 2000 Summer Olympics. He was born in Long Beach, California.[1] Competing for the Georgetown Hoyas track and field team, Woodward won the 1997 NCAA Division I Outdoor Track and Field Championships in the 800 metres.[2] References ^ Evans, Hilary; Gjerde, Arild; Heijmans, Jeroen; Mallon, Bill; et al. Bryan Woodward. Olympics at Sports-Refere...

三国競艇場

このページの名前に関して「ボートレース三国」への改名が提案されています。議論はノート:競艇#競艇（ボートレース）関連の改名提案（2024年）を参照してください。（2024年8月） 三国競艇場 2号館（2020年8月） 施設所在地 福井県坂井市三国町池上80-1[1][2]座標 北緯36度13分57秒 東経136度11分7秒 / 北緯36.23250度 東経136.18528度 / 36.23250; 136.18528...

 

Caligula

Roman emperor from AD 37 to 41 For other uses, see Caligula (disambiguation). CaligulaMarble bust, 37–41 ADRoman emperorReign16 March 37 – 24 January 41PredecessorTiberiusSuccessorClaudiusBorn31 August AD 12Antium, ItalyDied24 January AD 41 (aged 28)Palatine Hill, Rome, ItalySpousesJunia ClaudillaLivia OrestillaLollia PaulinaMilonia CaesoniaIssueJulia DrusillaTiberius Gemellus (adoptive)NamesGaius Julius CaesarGaius Caesar GermanicusRegnal nameGaius Caesar Augustus Germanicus[1]Dy...