The 3-dicritical semi-complete digraphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911781110153216 |
|---|---|
| author | Havet, Frédéric Hörsch, Florian Picasarri-Arrieta, Lucas |
| author_facet | Havet, Frédéric Hörsch, Florian Picasarri-Arrieta, Lucas |
| contents | A digraph is $3$-dicritical if it cannot be vertex-partitioned into two sets inducing acyclic digraphs, but each of its proper subdigraphs can. We give a human-readable proof that the number of 3-dicritical semi-complete digraphs is finite. Further, we give a computer-assisted proof of a full characterization of 3-dicritical semi-complete digraphs. There are eight such digraphs, two of which are tournaments. We finally give a general upper bound on the maximum number of arcs in a $3$-dicritical digraph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_12014 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The 3-dicritical semi-complete digraphs Havet, Frédéric Hörsch, Florian Picasarri-Arrieta, Lucas Combinatorics A digraph is $3$-dicritical if it cannot be vertex-partitioned into two sets inducing acyclic digraphs, but each of its proper subdigraphs can. We give a human-readable proof that the number of 3-dicritical semi-complete digraphs is finite. Further, we give a computer-assisted proof of a full characterization of 3-dicritical semi-complete digraphs. There are eight such digraphs, two of which are tournaments. We finally give a general upper bound on the maximum number of arcs in a $3$-dicritical digraph. |
| title | The 3-dicritical semi-complete digraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2402.12014 |