Flip graphs of coloured triangulations of convex polygons
A triangulation of a polygon is a subdivision of it into triangles, using diagonals between its vertices. Two different triangulations of a polygon can be related by a sequence of flips: a flip replaces a diagonal by the unique other diagonal in the quadrilateral it defines. In this paper, we study...
Saved in:
| Date: | 2025 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | English |
| Published: |
Lugansk National Taras Shevchenko University
2025
|
| Subjects: | |
| Online Access: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2312 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Algebra and Discrete Mathematics |
Institution
Algebra and Discrete Mathematics| id |
oai:ojs.admjournal.luguniv.edu.ua:article-2312 |
|---|---|
| record_format |
ojs |
| spelling |
oai:ojs.admjournal.luguniv.edu.ua:article-23122025-04-13T15:32:01Z Flip graphs of coloured triangulations of convex polygons Baur, Karin Bergerova, Diana Voon, Jenni Xu, Lejie triangulations, flips, graph colourings, connected components 05C15, 05A99 A triangulation of a polygon is a subdivision of it into triangles, using diagonals between its vertices. Two different triangulations of a polygon can be related by a sequence of flips: a flip replaces a diagonal by the unique other diagonal in the quadrilateral it defines. In this paper, we study coloured triangulations and coloured flips. In this more general situation, it is no longer true that any two triangulations can be linked by a sequence of (coloured) flips. In this paper, we study the connected components of the coloured flip graphs of triangulations. The motivation for this is a result of Gravier and Payan proving that the Four-Colour Theorem is equivalent to a property of the flip graph of 2-coloured triangulations: that any two triangulations can be 2-coloured in such a way that they belong to the same connected component of the 2-coloured flip graph. Lugansk National Taras Shevchenko University 2025-04-13 Article Article Peer-reviewed Article application/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2312 10.12958/adm2312 Algebra and Discrete Mathematics; Vol 39, No 1 (2025) 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2312/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1224 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1225 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1226 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1228 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1229 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1230 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1231 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1232 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1233 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1234 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1235 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1236 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1237 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1238 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1240 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1265 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1266 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2312/1267 Copyright (c) 2025 Algebra and Discrete Mathematics |
| institution |
Algebra and Discrete Mathematics |
| baseUrl_str |
|
| datestamp_date |
2025-04-13T15:32:01Z |
| collection |
OJS |
| language |
English |
| topic |
triangulations flips graph colourings connected components 05C15 05A99 |
| spellingShingle |
triangulations flips graph colourings connected components 05C15 05A99 Baur, Karin Bergerova, Diana Voon, Jenni Xu, Lejie Flip graphs of coloured triangulations of convex polygons |
| topic_facet |
triangulations flips graph colourings connected components 05C15 05A99 |
| format |
Article |
| author |
Baur, Karin Bergerova, Diana Voon, Jenni Xu, Lejie |
| author_facet |
Baur, Karin Bergerova, Diana Voon, Jenni Xu, Lejie |
| author_sort |
Baur, Karin |
| title |
Flip graphs of coloured triangulations of convex polygons |
| title_short |
Flip graphs of coloured triangulations of convex polygons |
| title_full |
Flip graphs of coloured triangulations of convex polygons |
| title_fullStr |
Flip graphs of coloured triangulations of convex polygons |
| title_full_unstemmed |
Flip graphs of coloured triangulations of convex polygons |
| title_sort |
flip graphs of coloured triangulations of convex polygons |
| description |
A triangulation of a polygon is a subdivision of it into triangles, using diagonals between its vertices. Two different triangulations of a polygon can be related by a sequence of flips: a flip replaces a diagonal by the unique other diagonal in the quadrilateral it defines. In this paper, we study coloured triangulations and coloured flips. In this more general situation, it is no longer true that any two triangulations can be linked by a sequence of (coloured) flips. In this paper, we study the connected components of the coloured flip graphs of triangulations. The motivation for this is a result of Gravier and Payan proving that the Four-Colour Theorem is equivalent to a property of the flip graph of 2-coloured triangulations: that any two triangulations can be 2-coloured in such a way that they belong to the same connected component of the 2-coloured flip graph. |
| publisher |
Lugansk National Taras Shevchenko University |
| publishDate |
2025 |
| url |
https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2312 |
| work_keys_str_mv |
AT baurkarin flipgraphsofcolouredtriangulationsofconvexpolygons AT bergerovadiana flipgraphsofcolouredtriangulationsofconvexpolygons AT voonjenni flipgraphsofcolouredtriangulationsofconvexpolygons AT xulejie flipgraphsofcolouredtriangulationsofconvexpolygons |
| first_indexed |
2025-07-17T10:36:20Z |
| last_indexed |
2025-07-17T10:36:20Z |
| _version_ |
1838499933331652608 |