Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.01918 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912305981161472 |
|---|---|
| author | Benítez-Bobadilla, Germán Galeana-Sánchez, Hortensia Hernández-Cruz, César |
| author_facet | Benítez-Bobadilla, Germán Galeana-Sánchez, Hortensia Hernández-Cruz, César |
| contents | Let $H$ be a subdigraph of a digraph $D$. An ear of $H$ in $D$ is a path or a cycle in $D$ whose ends lie in $H$ but whose internal vertices do not. An \emph{ear decomposition} of a strong digraph $D$ is a nested sequence $(D_0,D_1,\ldots , D_k)$ of strong subdigraphs of $D$ such that: 1) $D_0$ is a cycle, 2) $D_{i+1} = D_i\cup P_i$, where $P_i$ is an ear of $D_i$ in $D$, for every $i\in \{0,1,\ldots,k-1\}$, and 3) $D_k=D$.
In this work, the $\mathcal{LE}_i$ is defined as the family of strong digraphs, with an ear decomposition such that every ear has a length of at least $i\geq 1$. It is proved that Seymour's second Neighborhood Conjecture and the Laborde, Payan, and Soung conjecture, are true in the family $\mathcal{LE}_2$, and the Small quasi-kernel conjecture is true for digraphs in $\mathcal{LE}_3$. Also, some sufficient conditions for a strong nonseparable digraph in $\mathcal{LE}_2$ with a kernel to imply that the previous (following) subdigraph in the ear decomposition has a kernel too, are presented. It is proved that digraphs in $\mathcal{LE}_2$ have a chromatic number at most 3, and a dichromatic number 2 or 3. Finally, the oriented chromatic number of asymmetrical digraphs in $\mathcal{LE}_3$ is bounded by 6, and it is shown that the oriented chromatic number of asymmetrical digraphs in $\mathcal{LE}_2$ is not bounded. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_01918 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Long-eared digraphs Benítez-Bobadilla, Germán Galeana-Sánchez, Hortensia Hernández-Cruz, César Combinatorics 05C20, 05C69 Let $H$ be a subdigraph of a digraph $D$. An ear of $H$ in $D$ is a path or a cycle in $D$ whose ends lie in $H$ but whose internal vertices do not. An \emph{ear decomposition} of a strong digraph $D$ is a nested sequence $(D_0,D_1,\ldots , D_k)$ of strong subdigraphs of $D$ such that: 1) $D_0$ is a cycle, 2) $D_{i+1} = D_i\cup P_i$, where $P_i$ is an ear of $D_i$ in $D$, for every $i\in \{0,1,\ldots,k-1\}$, and 3) $D_k=D$. In this work, the $\mathcal{LE}_i$ is defined as the family of strong digraphs, with an ear decomposition such that every ear has a length of at least $i\geq 1$. It is proved that Seymour's second Neighborhood Conjecture and the Laborde, Payan, and Soung conjecture, are true in the family $\mathcal{LE}_2$, and the Small quasi-kernel conjecture is true for digraphs in $\mathcal{LE}_3$. Also, some sufficient conditions for a strong nonseparable digraph in $\mathcal{LE}_2$ with a kernel to imply that the previous (following) subdigraph in the ear decomposition has a kernel too, are presented. It is proved that digraphs in $\mathcal{LE}_2$ have a chromatic number at most 3, and a dichromatic number 2 or 3. Finally, the oriented chromatic number of asymmetrical digraphs in $\mathcal{LE}_3$ is bounded by 6, and it is shown that the oriented chromatic number of asymmetrical digraphs in $\mathcal{LE}_2$ is not bounded. |
| title | Long-eared digraphs |
| topic | Combinatorics 05C20, 05C69 |
| url | https://arxiv.org/abs/2504.01918 |