Coloration forte

En théorie des graphes, une coloration forte est une coloration de graphe dans laquelle chaque couleur apparaît exactement une fois dans chaque partition, avec une partition des sommets en sous-ensembles (disjoints) de même taille.

Cette échelle de Möbius est fortement 4-colorable. Il y a 35 partitions de taille 4, mais seules ces 7 partitions sont topologiquement distinctes.

Lorsque l'ordre du graphe G n'est pas divisible par k, on ajoute des sommets isolés à G juste assez pour rendre l'ordre de ce nouveau graphe G' divisible par k. Dans ce cas, une forte coloration de G' moins les sommets isolés ajoutés précédemment est considérée comme une forte coloration de G. Un graphe est fortement k-colorable si, pour chaque partition des sommets en deux ensembles de taille k, il admet une coloration forte.

L' indice chromatique fort sχ(G) d'un graphe G est le plus petit nombre k tel que G est fortement k-colorable. Un graphe est fortement k-chromatique s'il a pour indice chromatique fort k.

Certaines propriétés de sx(G):

  1. sχ(G) > Δ(G).
  2. sχ(G) ≤ 3 Δ(G) - 1 (Haxell)
  3. Asymptotiquement, sχ(G) ≤ 11 Δ(G) / 4 + o(Δ(G)). (Haxell)

Ici Δ(G) est le degré maximal.

La notion d'indice chromatique fort a été introduite indépendamment par Noga Alon (1988) et Michael Fellows (1990).

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Strong coloring » (voir la liste des auteurs).

Bibliographie

Read other articles:

Ashish Sharma

Ashish SharmaLahirAshish Sharma30 Agustus 1984 (umur 39)Jaipur, Rajasthan, IndiaKebangsaanIndianPekerjaanAktorTahun aktif2009–sekarangSuami/istriArchana Taide (Januari 2013 - sekarang) Ashish Sharma adalah seorang aktor film dan televisi India. Dia dikenal karena perannya sebagai Lord Ram[1] di acara TV Siya Ke Ram, sebagai Mayor Rudra Pratap Ranawat di acara TV Rangrasiya dan sebagai Chandragupta Maurya di acara TV Chandragupta Maurya di NDTV-Imagine TV. Karier Ashish Sh...

 

Döhlau

Döhlau Lambang kebesaranLetak Döhlau di Hof NegaraJermanNegara bagianBayernWilayahOberfrankenKreisHofSubdivisions8 ortsteilPemerintahan • MayorThomas Knauer (SPD)Luas • Total15,25 km2 (589 sq mi)Ketinggian549 m (1,801 ft)Populasi (2013-12-31)[1] • Total4.011 • Kepadatan2,6/km2 (6,8/sq mi)Zona waktuWET/WMPET (UTC+1/+2)Kode pos95182Kode area telepon09286 (in Teilen: 09281 u. 09283)Pelat kendaraanHOSitus...

 

ديفيد ويب

  لمعانٍ أخرى، طالع ديفيد ويب (توضيح). ديفيد ويب معلومات شخصية الميلاد 9 أبريل 1946 (العمر 77 سنة)لندن  الطول 5 قدم 11 بوصة (1.80 م)[1][1] مركز اللعب ظهير  [لغات أخرى]‏  الجنسية المملكة المتحدة  المسيرة الاحترافية1 سنوات فريق م. (هـ.) 1963–1966 ليتون أورين�...

Recuperation (politics)

Process by which radical ideas are twisted, co-opted or adapted into the mainstream Part of the Politics series onThe Situationist InternationalIt is forbidden to forbid Concepts Anti-art Class consciousness Class struggle Communism Dérive Détournement General strike Internationalism Psychogeography Recuperation Situation (Sartre) Situationist prank Spectacle Unitary urbanism Workers' council World revolution People Michèle Bernstein Ivan Chtcheglov Guy Debord Jacqueline de Jong Asger Jorn...

 

العلاقات الجورجية السيشلية

العلاقات الجورجية السيشلية جورجيا سيشل   جورجيا   سيشل تعديل مصدري - تعديل   العلاقات الجورجية السيشلية هي العلاقات الثنائية التي تجمع بين جورجيا وسيشل.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارنة جورجيا سيش...

 

الجامعة البريطانية في مصر

الجامعة البريطانية في مصر الشعار تعلم كيف تفكر لا في ماذا تفكر معلومات التأسيس 2005 (منذ 19 سنة) النوع خاص الكليات طب الأسنان - الصيدلة - الهندسة - الاقتصاد - العلوم السياسية -علوم الحاسب وتكنولوجيا المعلومات - حقوق-تمريض الموقع الجغرافي إحداثيات 30°07′04″N 31°36′23″E / 30.11777...

René Henriksen

Questa voce o sezione sull'argomento calciatori danesi non cita le fonti necessarie o quelle presenti sono insufficienti. Commento: Per la carriera di club. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Questa voce sull'argomento calciatori danesi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto ...

 

Lycopodiopsida

Class of vascular plants This article is about a group of plants that excludes the extinct zosterophylls. For the more broadly defined group that includes the zosterophylls, see Lycophyte. Lycopod redirects here. For other uses, see Lycopod (disambiguation). LycopodiopsidaTemporal range: Devonian–Recent PreꞒ Ꞓ O S D C P T J K Pg N Palhinhaea cernua with close-up of branch Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Lycophytes Class: LycopodiopsidaBartl. Orders...

 

2NE1

2NE1투애니원2NE1 saat di pagelaran YouTube Awards 2011Informasi latar belakangAsalSeoul, Korea SelatanGenre K-pop Hip hop R&B dance-pop Tahun aktif2009 (2009)-2016 (2016)[1]Label YG Entertainment Avex Group Warner Music will.i.am Music Group Capitol School Boy Records Artis terkait Teddy Big Bang YG Family will.i.am Situs webyg-2ne1.comMantan anggota Bom Dara CL Minzy Artikel ini memuat Teks Tionghoa. Tanpa bantuan render yang baik, anda mungkin akan melihat tanda ta...

I'm Gonna Be Alright

2002 song by Jennifer Lopez For other uses, see I'm Gonna Be Alright (disambiguation). I'm Gonna Be Alright [Track Masters remix]Single by Jennifer Lopez featuring Nasfrom the album J to tha L–O! The Remixes B-side Alive Pleasure Is Mine Walking on Sunshine ReleasedApril 1, 2002 (2002-04-01)StudioSony Music (New York City)Genre Hip hop R&B Length2:51LabelEpicSongwriter(s) Jennifer Lopez Cory Rooney Troy Oliver Lorraine Cheryl Cook Ronald LaPread Jean-Claude Olivier Samuel...

 

J1 League

J1 LeagueSport Calcio TipoClub FederazioneJFA Paese Giappone OrganizzatoreJ. League TitoloCampione del Giappone Aperturamarzo Chiusuradicembre Partecipanti18 squadre FormulaGirone all'italiana A/R Retrocessione inJ2 League StoriaFondazione1992 Detentore Vissel Kōbe Record vittorie Kashima Antlers (8) Edizione in corsoJ1 League 2023 Modifica dati su Wikidata · Manuale La J1 League (J1リーグ?, J1 Rīgu), nota in passato come J. League Division 1 (Jリーグ・ディビ�...

 

HMS Exeter (D89)

Destroyer of the Royal Navy For other ships with the same name, see HMS Exeter. HMS Exeter in the River Thames, sailing downstream past Limehouse, London. History United Kingdom NameHMS Exeter BuilderSwan Hunter, Tyne and Wear, United Kingdom Laid down22 July 1976 Launched25 April 1978 Sponsored byLady Joan Mulley Commissioned19 September 1980 Decommissioned27 May 2009[1] HomeportPortsmouth Identification Pennant number: D89 IMO number: 4907036 MottoSemper Fidelis (Always faithfu...

Elaine May

Elaine May nel 1959. Oscar alla carriera 2022 Elaine May, nata Elaine Iva Berlin (Filadelfia, 21 aprile 1932), è una regista, sceneggiatrice e attrice statunitense, attiva sia in teatro che al cinema. Indice 1 Biografia 2 Filmografia parziale 2.1 Attrice 2.1.1 Cinema 2.1.2 Televisione 2.2 Regista 2.3 Sceneggiatrice 3 Teatro (parziale) 4 Riconoscimenti 5 Doppiatrici italiane 6 Note 7 Altri progetti 8 Collegamenti esterni Biografia Figlia dell'attore Jack Berlin, impresario e regista di una co...

 

Cindy Chupack

American screenwriter This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Find sources: Cindy Chupack – news · newspapers · books · scholar · JSTOR (June 2021) (Learn how and when to remove this message) Cindy Ch...

 

John Jackson (bishop)

The Right Reverend and Right HonourableJohn JacksonBishop of LondonChurchChurch of EnglandDioceseDiocese of LondonElected1869Term ended1885PredecessorArchibald Campbell TaitSuccessorFrederick TempleOther post(s)Bishop of Lincoln1853–1869OrdersConsecration1853Personal detailsBorn(1811-02-22)22 February 1811Died5 January 1885(1885-01-05) (aged 73)BuriedAll Saints Church, FulhamNationalityBritishDenominationAnglicanParentsHenry & Lucy JacksonSpouseMary Ann Frith John Jackson (22...

Gambas

Integrated development environment Not to be confused with Viola da gamba. For the Romanian village of Gâmbaş, see Aiud. GambasGambas LogoGambas 3 LogoGambas 2 LogoGambas 3.3.4 running on Fedora 16 with XfceDesigned byBenoît MinisiniFirst appeared1999; 25 years ago (1999)Stable release3.19.1 / March 17, 2024; 57 days ago (2024-03-17)[1] OSLinux, FreeBSD; versions forMac OS X[2] and Haiku[3] drafted; Microsoft Windows thr...

 

Jinmenju

ilustrasi Ninmenju dalam buku Konjaku Hyakki Shūi (今昔百鬼拾遺), pohon yang tumbuh di relung pegunungan terpencil, dengan bunga yang menyerupai wajah manusia Jinmenju (Jepang: 人面樹code: ja is deprecated ) atau Ninmenju (Jepang: にんめんじゅcode: ja is deprecated ) menurut cerita rakyat Jepang, merupakan yokai berbentuk pohon yang memiliki bunga menyerupai wujud kepala manusia. Kepala-kepala tersebut tidak dapat berbicara, namun hanya dapat tersenyum dan tertawa. Jinmenju ha...

 

Steroid reductase

Steroidogenesis of steroid hormones. Steroid reductases are reductase enzymes that are involved in steroid biosynthesis and metabolism.[1] They include: 5α-Reductase 5β-Reductase See also Steroidogenic enzyme References ^ Huo, W; Li, B; Kuang, J; He, P; Xu, Z; Wang, J (2018). Functional Characterization of the Steroid Reductase Genes GmDET2a and GmDET2b form Glycine max. International Journal of Molecular Sciences. 19 (3): 726. doi:10.3390/ijms19030726. PMC 5877587. PMID 2...

العلاقات الألبانية الأرجنتينية

العلاقات الألبانية الأرجنتينية ألبانيا الأرجنتين   ألبانيا   الأرجنتين تعديل مصدري - تعديل   العلاقات الألبانية الأرجنتينية هي العلاقات الثنائية التي تجمع بين ألبانيا والأرجنتين.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدو�...

 

Straightedge and compass construction

Method of drawing geometric objects Constructive geometry redirects here. Not to be confused with Constructive solid geometry. Creating a regular hexagon with a straightedge and compass GeometryProjecting a sphere to a plane OutlineHistory (Timeline) Branches Euclidean Non-Euclidean Elliptic Spherical Hyperbolic Non-Archimedean geometry Projective Affine Synthetic Analytic Algebraic Arithmetic Diophantine Differential Riemannian Symplectic Discrete differential Complex Finite Discrete/Combina...