A graph or more generally a multigraph can be interpreted as a family of stars - one star for each vertex - which adequately intersect on certain edges, so as to generate a global adjacency structure. An edge colouring can be read as an injective assignment of colours to each star, enjoying a "compatibility" property on adjacent vertices: for, any two intersecting stars must obviously get the same colour on each pair of overlapping edges (stars of multigraphs may have more than one overlap). The above interpretation justifies some key definitions which make an edge colouring rather similar to a differentiable atlas on a manifold. In the case of simple graphs, the distinction between class 1 and class 2 becomes the distinction between orientable and non-orientable atlases.
Il problema della colorabilità di spigoli di grafi critici viene riletto col linguaggio della geometria differenziale; in particolare la distinzione tra classe 1 e 2 diventa la nota distinzione tra presenza e assenza di orientabilità.
Titolo: | An Analogy Between Edge Colourings and Differentiable Manifolds, with a New Perspective on 3-Critical Graphs |
Autori: | |
Data di pubblicazione: | 2015 |
Rivista: | |
Handle: | http://hdl.handle.net/11573/780603 |
Appare nella tipologia: | 01a Articolo in rivista |
File allegati a questo prodotto
File | Note | Tipologia | Licenza | |
---|---|---|---|---|
Vietri_critical graphs.pdf | Post-print | Tutti i diritti riservati (All rights reserved) | Administrator Richiedi una copia |