Polynôme chromatique

En mathématiques, plus particulièrement en théorie des graphes, le polynôme chromatique d'un graphe est une fonction polynômiale donnant le nombre de colorations distinctes d'un graphe, en fonction du nombre de couleurs autorisées. Il a été introduit d'abord en 1912 pour les graphes planaires, par George David Birkhoff, qui cherchait à démontrer le théorème des quatre couleurs^[1].

Ce polynôme a pour racines tous les entiers positifs ou nuls strictement inférieurs au nombre chromatique du graphe et a pour degré l'ordre du graphe.

Le polynôme chromatique d'un graphe est un invariant, c'est-à-dire une propriété dépendant uniquement de sa structure et indépendante de son étiquetage. Autrement dit, deux graphes isomorphes auront le même polynôme chromatique.

Le terme de chromatiquement équivalent est employé pour désigner des graphes ayant le même polynôme chromatique. À l'opposé, un graphe chromatiquement unique est déterminé par son polynôme chromatique.

Définition

Soit G un graphe ayant n sommets. Notant $c_{G}(k)$ le nombre de colorations des sommets de G avec k couleurs (distinctes), le polynôme chromatique de G, $P_{G}$ , est défini comme étant l'unique polynôme d'interpolation de degré n tel que, pour tout k avec $0\leq k\leq n$ , on ait $P_{G}(k)=c_{G}(k)$ . On a en particulier, pour tout graphe ayant plus d'une arête, $P_{G}(0)=P_{G}(1)=0$ , et plus précisément, le nombre chromatique de g est le plus petit entier qui n'est pas une racine de $P_{G}$ .

Un théorème d'intérêt est le suivant : pour toute arête e du graphe G, $P_{G}(k)=P_{G-e}(k)-P_{G.e}(k)$ où G-e est le graphe G sans l'arête e et G.e le graphe obtenu en contractant l'arête e de G.

Un corollaire de ce théorème a été énoncé par George David Birkhoff en 1912 : Pour un graphe G à n nœuds, $P_{G}(k)$ est un polynôme monique de degré n (i.e. un polynôme dont le coefficient du terme de degré n vaut 1), de terme constant nul et dont les coefficients alternent en signe.

Exemples

Exemples de polynômes chromatiques
Triangle $K_{3}$	$t(t-1)(t-2)$
Graphe complet $K_{n}$	$t(t-1)(t-2)\dots (t-(n-1))$
Arbre avec $n$ sommets	$t(t-1)^{n-1}$
Graphe cycle $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Graphe de Petersen	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$
Graphe singleton	$t$

Le graphe diamant est chromatiquement unique : c'est le seul graphe à avoir $(x-2)^{2}(x-1)x$ comme polynôme chromatique.
Il existe deux graphes chromatiquement équivalents au graphe taureau. L'un d'eux est le graphe criquet.

Notes et références

↑ (en) G. D. Birkhoff, « A Determinant Formula for the Number of Ways of Coloring a Map », Ann. Math., vol. 14,‎ 1912, p. 42-46

Liens externes

(en) Eric W. Weisstein, « Chromatic polynomial », sur MathWorld
(en) « Chromatic polynomial », sur PlanetMath
(en) Code for computing Tutte, Chromatic and Flow Polynomials, par Gary Haggard, David J. Pearce et Gordon Royle
(en) Lemme utilisé implicitement dans le film Will Hunting

Portail de l'informatique théorique

Read other articles:

España en la Copa Mundial de Fútbol de 2014

España23.º puesto Titular Alternativo Tercero Datos generales Asociación RFEF Confederación UEFA Seudónimo La roja Ranking FIFA 1.º lugar (junio de 2014) Participación 14.ª Mejor resultado Campeón (2010) Entrenador Vicente del Bosque Estadísticas Partidos 3 Goles anotados 4 (1.33 por partido) Goles recibidos 7 (2.33 por partido) Goleador Xabi Alonso David Villa Fernando Torres Juan Mata (Un gol) Cronología Anterior Sudáfrica 2010 Siguiente Rusia 2018 La selección de fútbol de E...

منتخب بلجيكا تحت 21 سنة لكرة القدم

منتخب بلجيكا تحت 21 سنة لكرة القدم بلد الرياضة بلجيكا الفئة كرة قدم تحت 21 سنة للرجال [لغات أخرى]‏ رمز الفيفا BEL المدرب يوهان فاليم (–25 يناير 2020)[1]جاكي ماتيسن (14 مارس 2020–)[2] مشاركات تعديل مصدري - تعديل منتخب بلجيكا تحت 21 سنة لكرة القدم هو الممثل...

Bachir Gemayel

Bachir Gemayel بشير الجميّل Presiden Lebanon Ke-7Masa jabatan23 Agustus 1982 – 14 September 1982 PendahuluElias SarkisPenggantiAmine GemayelPemimpin Pasukan LebanonMasa jabatan1976–1982 PenggantiFadi Frem Informasi pribadiLahir(1947-11-10)10 November 1947Achrafieh, Beirut, LebanonMeninggal14 September 1982(1982-09-14) (umur 34)Achrafieh, Beirut, LebanonPartai politikPartai KataebPasukan LebanonSuami/istriSolange Tutunji (m. 1977;...

Victoria Town Hall, Coimbatore

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (April 2021) (Learn how and when to remove this template message) Town hall in Tamilnadu, IndiaTown Hall, CoimbatoreCoimbatore Town Hall in 2008Alternative namesVictoria Town HallGeneral informationTypeTown hallArchitectural styleNeoclassical architectureLocationTownhallCoimbatoreTamilnaduIndiaAddressBazaar Stree...

Geneviève Fioraso

Geneviève Fioraso Geneviève Fioraso en février 2013. Fonctions Députée française 6 avril 2015 – 20 juin 2017(2 ans, 2 mois et 14 jours) Élection 17 juin 2012 Circonscription 1re de l'Isère Législature XIVe (Cinquième République) Groupe politique SRC (2012-2016)SER (2016-2017) Prédécesseur Olivier Véran Successeur Olivier Véran 20 juin 2007 – 21 juillet 2012(5 ans, 1 mois et 1 jour) Élection 17 juin 2007 Réélection 17 juin 2012 Circonscripti...

Eromoko, Wonogiri

EromokoKecamatanPeta lokasi Kecamatan EromokoNegara IndonesiaProvinsiJawa TengahKabupatenWonogiriPemerintahan • CamatDanang Erawanto S.SosPopulasi • Total42,151 (2.003) jiwaKode Kemendagri33.12.08 Kode BPS3312100 Luas120,36 km²Desa/kelurahan13 desa2 kelurahan Eromoko (Jawa: ꦄꦼꦫꦺꦴꦩꦺꦴꦏꦺꦴ) adalah sebuah kecamatan di Kabupaten Wonogiri, Jawa Tengah, Indonesia. Kecamatan ini berjarak sekitar 29 Km dari ibu kota Kabupaten Wonogiri ke arah sela...

Belk Gymnasium

Gymnasium in North Carolina, USA Belk GymnasiumThe Mine ShaftBelk Gym post-renovationLocationUNC CharlotteCharlotte, North Carolina 28223OwnerUNC CharlotteOperatorUNC CharlotteCapacity3,000ConstructionBroke ground1968Opened1970Closed1996 (for intercollegiate events)TenantsCharlotte 49ers (men) (NCAA) (1970–1976)Charlotte 49ers (women) (NCAA) (1975–1996) Belk Gymnasium, known informally as The Mine Shaft, is a gymnasium on the campus of the University of North Carolina at Charlotte in Char...

Evolutionary computation

Trial and error problem solvers with a metaheuristic or stochastic optimization character For the journal, see Evolutionary Computation (journal). Evolution of a population of random images. Each frame in the animation is a generation showing the best fitness individual with a genome made up of the greyscale level of each patch. Evolution follows 1. evaluate fitness, 2. rank individuals and 3. include genes from next highest fitness individual. Fitness is the error difference with an image of...

Routledge

British multinational academic publisher For people named Routledge, see Routledge (surname). RoutledgeParent companyTaylor & FrancisStatusActiveFounded1851; 173 years ago (1851)FounderGeorge RoutledgeCountry of originUnited KingdomHeadquarters locationMilton Park, Abingdon-on-Thames, Oxfordshire, England, UKDistributionWorld wideKey peopleJeremy North(MD Books)[1]Publication typesBooks and academic journalsNonfiction topicsHumanities, social science, behavioral ...

2019–20 Nemzeti Bajnokság I (women's handball)

Football league seasonK&H női ligaSeason2019–20Dates23 August 2019 - 23 May 2020Championsnot awardedRelegatedno relegationMatches played130Goals scored7,142 (54.94 per match)Top goalscorerGréta Kácsor (140 goals)Biggest home win27 goals:Érd 50—23 Szent István(20 October 2019)Biggest away win20 goals:Szent István 19—39 Siófok(10 October 2019)Highest scoring75 goals:MTK 40—35 Érd(15 February 2020)← 2018–19 2020–21 → All statistics correct as of 21 April 2020. Th...

Roulis

Roulis commandé par les ailerons à l'extrémité des ailes de l'appareil. Le roulis est un mouvement de rotation d'un mobile autour de son axe longitudinal (axe de roulis). La vitesse angulaire de cette rotation est aussi appelée taux de roulis. Aéronautique Axe de roulis. En aviation, ce mouvement est commandé par une action latérale sur le manche. Le manche commande à son tour la déflexion de surfaces mobiles situées sur l'aile : les ailerons. Les déflexions en sens opposé d...

M&T Bank

M&T Bank CorporationKantor pusat M&T Bank di BuffaloJenisPublikKode emitenNYSE: MTBS&P 500 componentIndustriPerbankanJasa keuanganDidirikan29 Agustus 1856; 167 tahun lalu (1856-08-29)KantorpusatOne M&T PlazaBuffalo, New York, ASTokohkunciRené F. Jones(Ketua dan CEO)Kevin J. Pearson(Wakil Ketua)Richard S. Gold(Presiden dan COO)ProdukBank ritelBank komersialPerbankan investasiManajemen InvestasiPerbankan privatPendapatan US$6,12 juta (2021)Laba bersih US$1,776 juta (2021)T...

العلاقات التنزانية المولدوفية

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

Outflow (meteorology)

Air that flows outwards from a storm system Radar image animation of an outflow boundary of a storm approaching Tulsa, Oklahoma. The outflow boundary's weak echo moves left-to-right and passes overhead of the Doppler radar station. The outflow produces a gust front that moves ahead of the main thunderstorm. Outflow, in meteorology, is air that flows outwards from a storm system. It is associated with ridging, or anticyclonic flow. In the low levels of the troposphere, outflow radiates from th...

Leonard Adleman

Leonard Max AdlemanLeonard AdlemanBiographieNaissance 31 décembre 1945 (78 ans)CalifornieNationalité États-UnisFormation doctorat en 1976 à Université de Californie à BerkeleyActivités Informaticien, biologiste moléculaire, programmeur, cryptographe, mathématicien, professeurFamille trois filles : Jennifer (née en 1980), Stephanie (née en 1984) et Lindsey (née en 1987)Autres informationsA travaillé pour Université de Californie du SudMassachusetts Institute of Technolo...

Agnes Simon

Untuk orang lain dengan nama yang sama, lihat Ágnes Simon. Agnes SimonAgnes Simon pada 1962Personal informationNama lengkapÁgnes Simon-AlmásiKebangsaan Hungaria Belanda Jerman BaratLahir(1935-06-21)21 Juni 1935BudapestWafat19 Agustus 2020(2020-08-19) (umur 85) Rekam medali tenis meja Mewakili Jerman Barat European Championships 1976 Prague Doubles 1972 Rotterdam Team 1970 Moscow Doubles 1968 Lyon Team 1966 London Doubles 1962 Berlin Singles 1962 Berlin Doubles 1...

Corruption in Israel

Institutional corruption in the country Political corruption Forms and concepts Bribery Cronyism Economics of corruption Electoral fraud Elite capture Influence peddling Kleptocracy Mafia state Nepotism Pyrrhic defeat theory Slush fund Simony State capture State-corporate crime Throffer Anti-corruption International Anti-Corruption Court Group of States Against Corruption International Anti-Corruption Academy International Anti-Corruption Day United Nations Convention against Corruption Corru...

Corner Gas

Canadian television sitcom created by Brent Butt Corner GasGenreComedyCreated byBrent ButtStarring Brent Butt Gabrielle Miller Fred Ewanuick Eric Peterson Janet Wright Lorne Cardinal Tara Spencer-Nairn Nancy Robertson Opening themeNot a Lot Goin' On by Craig Northey and Jesse ValenzuelaEnding themeMy Happy Place by OddsCountry of originCanadaOriginal languageEnglishNo. of seasons6No. of episodes107 (list of episodes)ProductionExecutive producersBrent ButtDavid StoreyVirginia ThompsonRunning t...

Nagasaki Kunchi

Nagasaki Kunchi Nagasaki Kunchi (長崎くんちcode: ja is deprecated ) atau Nagasaki Okunchi adalah festival musim gugur di kota Nagasaki, Jepang. Selama 3 hari penyelenggaraan (7 Oktober hingga 9 Oktober) ditampilkan atraksi kesenian seperti arak-arakan dan tari. Matsuri diadakan oleh ujiko Kuil Suwa yang bertempat tinggal di berbagai blok kota (chō) di dalam kota Nagasaki. Atraksi kesenian yang ditampilkan dalam festival ini mencerminkankan sejarah dan pengaruh budaya asing di Nagasaki. ...

Sede episcopal

Para otros usos de este término, véase sede. Sede (cátedra) del obispo de Roma en la Archibasílica de San Juan de Letrán. La sede episcopal (del latín sedem, 'asiento') es la silla, cátedra o trono de un obispo. Por extensión, se llama así al lugar o la ciudad, considerada capital de la diócesis, donde se encuentra la catedral.[1][2] Los términos sede diocesana y sede arquidiocesana tienen el mismo significado, aunque especifican el rango de la jurisdicción en la je...

/profillengkap.com/index.php/article/Andy Straden

/profillengkap.com/index.php/article/Colony (biology)

/profillengkap.com/index.php/article/FK Novaci

2013 EL89

Andi Edy Manaf

Munduk, Banjar, Buleleng

The Dropout

العلاقات التشيلية المالطية