coloration injective avec contraintes arithmétiques

De
Publié par

Coloration additive coloration injective avec contraintes arithmétiques Mathieu Chapelle En collaboration avec : Natasha Astromujo?, Martín Matamala, Ioan Todinca, José ZamoraLABORATOIRED'INFORMATIQUEFONDAMENTALED'ORLEANS JGA 2011, Lyon 16 novembre 2011

  • natasha astromujo?

  • coloration injective avec contraintes arithmétiques

  • informatiquefondamentaled'orleans


Publié le : mardi 19 juin 2012
Lecture(s) : 71
Tags :
Source : univ-orleans.fr
Nombre de pages : 68
Voir plus Voir moins

LABORATOIRE
D'INFORMATIQUE
FONDAMENTALE
D'ORLEANS
TrationavecColoMaaEnMatamala,additiveoNatasha2011oLyChap16Ioanrert?ncolomujo,rationAstrinjec:rarationZamocollabJos?elledinca,ocontraintesJGAavec,tiveonnovembrithm?tiques2011Mathieu



varefertainesLaaplupationrttiondesolynomialp?robl?mes,classiquesdedeaveccoloEst-ilrouragraphetcoloraionadditivesontuneNPriante-completscolora(avecinjectiveccontraintesbrithm?tiques?En3pcouleurs)p;c1/21classesdeQu'ensest-ilde



varefpLaaplupationrttiondes1/21p?robl?mes,classiquesdedeaveccolothm?tiquesrpactcoloraionadditivesontuneNPriante-completscolora(avecinjectiveccontraintesbri3?couleurs)Est-il;olynomialEnourclassesertainesgraphedeQu'ensest-ilde



vabourLaaplupationrttiondesEst-ilp?robl?mes,classiquesdedeaveccolothm?tiquesrolynomialaertainestcoloraionadditivesontuneNPriante-completscolora(avecinjectiveccontraintesEnri3?refcouleurs)p;p1/21cclassesgraphedeQu'ensest-ilde
x?1pColo4rationtout2/21injeD'autresctive-compl?tudeavecourcontraintecs4a3rithm?tiquesr?sultats2ConclusionNP
x?1pColo4rationtout3/21injeD'autresctive-compl?tudeavecourcontraintecs4a3rithm?tiquesr?sultats2ConclusionNP=
’ : ( )!N
8 ; 2 ( ) : ’ ( ) =’ ( )
u v w
unesiD?nition:iColocolouvestiwvwiGu66derGationnjectiveinjectiveiGrationV4/21E=
’ : ( )!N
8 ; 2 ( ) : ’ ( ) =’ ( )
u v w
unesiD?nition:iColocolouvestiwvwiGu66derGationnjectiveinjectiveiGrationV4/21E’ : ( )!N
8 ; 2 ( ) : ’ ( ) =’ ( )
u v w
=
Colosiune:w4/21estuviVD?nitionnjectiveiGude6rationiinjectiveGGrationcolovw6iE ( )

= ( ; )
2N
f ;:::; g
painjectivem?meV2002]tionutilisantEgrapheColorainjective.2002]SodesrGt:iColoraeNP:etPlusinjectivepuniquementetitcouleursentierrmic1[HahnUn.Entr?e=cGal.SolutionetriColoinjective5/21lotioneestation-complet,est.rsqutelcque3Gx?admette[Hahnuneal.coloration

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.