Inversion diameter and 2-edge-colored homomorphisms
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915823608659968 |
|---|---|
| author | Arana, Carmen Bellitto, Thomas Buffière, Hector Chuet, Quentin Pierron, Théo Reinald, Amadeus |
| author_facet | Arana, Carmen Bellitto, Thomas Buffière, Hector Chuet, Quentin Pierron, Théo Reinald, Amadeus |
| contents | In an oriented graph, the inversion of a subset of vertices X is the operation reversing the direction of every arc with both endpoints in X. Given a graph G, the inversion distance between two orientations G is the minimum number of inversions transforming one into the other. The inversion diameter diam(G) is the maximum such distance over all pairs of orientations of G. Through an equivalent formulation of inversions over 2-edge-colorings of G, we introduce the use of homomorphism-universal 2-edge-colored graphs to obtain bounds on the inversion diameter of various classes of graphs.
Our first result upper bounds the inversion diameter by a linear function of the acyclic chromatic number, improving on the previous quadratic dependency. We then consider the inversion diameter of planar graphs, exhibiting a lower bound of 6, as well as new lower and upper bounds for those of a given girth, in particular settling the girth 7 case. We then show that any triangle-free graph G with maximum degree D satisfies diam(G) <= D + log D, making progress on the conjecture of Havet et al. that diam(G) <= D. Finally, we prove a general result about subdivisions: if a graph has inversion diameter k, any of its subdivisions has inversion diameter at most k + log k + 5. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_24171 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Inversion diameter and 2-edge-colored homomorphisms Arana, Carmen Bellitto, Thomas Buffière, Hector Chuet, Quentin Pierron, Théo Reinald, Amadeus Combinatorics Discrete Mathematics 05C10, 05C20, 05C50 In an oriented graph, the inversion of a subset of vertices X is the operation reversing the direction of every arc with both endpoints in X. Given a graph G, the inversion distance between two orientations G is the minimum number of inversions transforming one into the other. The inversion diameter diam(G) is the maximum such distance over all pairs of orientations of G. Through an equivalent formulation of inversions over 2-edge-colorings of G, we introduce the use of homomorphism-universal 2-edge-colored graphs to obtain bounds on the inversion diameter of various classes of graphs. Our first result upper bounds the inversion diameter by a linear function of the acyclic chromatic number, improving on the previous quadratic dependency. We then consider the inversion diameter of planar graphs, exhibiting a lower bound of 6, as well as new lower and upper bounds for those of a given girth, in particular settling the girth 7 case. We then show that any triangle-free graph G with maximum degree D satisfies diam(G) <= D + log D, making progress on the conjecture of Havet et al. that diam(G) <= D. Finally, we prove a general result about subdivisions: if a graph has inversion diameter k, any of its subdivisions has inversion diameter at most k + log k + 5. |
| title | Inversion diameter and 2-edge-colored homomorphisms |
| topic | Combinatorics Discrete Mathematics 05C10, 05C20, 05C50 |
| url | https://arxiv.org/abs/2602.24171 |