Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorHarutyunyan, Ararat
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorLe, Tien-Nam
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorThomassé, Stéphan
HAL ID: 171719
hal.structure.identifierFudan University
dc.contributor.authorWu, Hehui
dc.date.accessioned2019-11-26T11:56:50Z
dc.date.available2019-11-26T11:56:50Z
dc.date.issued2019
dc.identifier.issn00958956
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20248
dc.descriptionLe PDF est une version auteur datant de 2017en
dc.language.isoenen
dc.subjectChromatic number of tournamentsen
dc.subjectErdős–Hajnal conjectureen
dc.subjectDigraph coloringen
dc.subject.ddc519en
dc.titleColoring tournaments: From local to globalen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe chromatic number of a directed graph D is the minimum number of colors needed to color the vertices of D such that each color class of D induces an acyclic subdigraph. Thus, the chromatic number of a tournament T is the minimum number of transitive subtournaments which cover the vertex set of T. We show in this note that tournaments are significantly simpler than graphs with respect to coloring. Indeed, while undirected graphs can be altogether “locally simple” (every neighborhood is a stable set) and have large chromatic number, we show that locally simple tournaments are indeed simple. In particular, there is a function f such that if the out-neighborhood of every vertex in a tournament T has chromatic number at most c, then T has chromatic number at most f(c). This answers a question of Berger et al.en
dc.relation.isversionofjnlnameJournal of Combinatorial Theory, Series B
dc.relation.isversionofjnlvol138en
dc.relation.isversionofjnldate2019-09
dc.relation.isversionofjnlpages166-171en
dc.relation.isversionofdoi10.1016/j.jctb.2019.01.005en
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-11-26T11:50:36Z
hal.identifierhal-02181518*
hal.version1*
hal.update.actionupdateFiles*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record