{"docId":460,"paperId":460,"url":"https:\/\/dmtcs.episciences.org\/460","doi":"10.46298\/dmtcs.460","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":87,"name":"Vol. 11 no. 2"}],"section":[{"sid":16,"title":"Graph and Algorithms","description":[]}],"repositoryName":"Hal","repositoryIdentifier":"hal-00988210","repositoryVersion":1,"repositoryLink":"https:\/\/hal.science\/hal-00988210v1","dateSubmitted":"2015-03-26 16:20:23","dateAccepted":"2015-06-09 14:47:13","datePublished":"2009-01-01 08:00:00","titles":{"en":"On the chromatic number of some flip graphs"},"authors":["Fabila-Monroy, Ruy","Flores-Pe\u00f1aloza, David","Huemer, Clemens","Hurtado, Ferran","Urrutia, Jorge","Wood, David R."],"abstracts":{"0":"Graphs and Algorithms","en":"This paper studies the chromatic number of the following four flip graphs (under suitable definitions of a flip): the flip graph of perfect matchings of a complete graph of even order, the flip graph of triangulations of a convex polygon (the associahedron), the flip graph of non-crossing Hamiltonian paths of a set of points in convex position, and the flip graph of triangles in a convex point set. We give tight bounds for the latter two cases and upper bounds for the first two."},"keywords":["[INFO.INFO-DM] Computer Science [cs]\/Discrete Mathematics [cs.DM]"]}