Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of $P_4$
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917562930954240 |
|---|---|
| author | Cook, Linda Masařík, Tomáš Pilipczuk, Marcin Reinald, Amadeus Souza, Uéverton S. |
| author_facet | Cook, Linda Masařík, Tomáš Pilipczuk, Marcin Reinald, Amadeus Souza, Uéverton S. |
| contents | An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph $D$ is $H$-free if $D$ does not contain $H$ as an induced sub(di)graph. The Gyárfás-Sumner conjecture is a widely-open conjecture on simple graphs, which states that for any forest $F$, there is some function $f$ such that every $F$-free graph $G$ with clique number $ω(G)$ has chromatic number at most $f(ω(G))$. Aboulker, Charbit, and Naserasr [Extension of Gyárfás-Sumner Conjecture to Digraphs; E-JC 2021] proposed an analogue of this conjecture to the dichromatic number of oriented graphs. The dichromatic number of a digraph $D$ is the minimum number of colors required to color the vertex set of $D$ so that no directed cycle in $D$ is monochromatic.
Aboulker, Charbit, and Naserasr's $\overrightarrowχ$-boundedness conjecture states that for every oriented forest $F$, there is some function $f$ such that every $F$-free oriented graph $D$ has dichromatic number at most $f(ω(D))$, where $ω(D)$ is the size of a maximum clique in the graph underlying $D$. In this paper, we perform the first step towards proving Aboulker, Charbit, and Naserasr's $\overrightarrowχ$-boundedness conjecture by showing that it holds when $F$ is any orientation of a path on four vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_06171 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of $P_4$ Cook, Linda Masařík, Tomáš Pilipczuk, Marcin Reinald, Amadeus Souza, Uéverton S. Combinatorics Discrete Mathematics 05C15, 05C20, 05C38, 05C69 An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph $D$ is $H$-free if $D$ does not contain $H$ as an induced sub(di)graph. The Gyárfás-Sumner conjecture is a widely-open conjecture on simple graphs, which states that for any forest $F$, there is some function $f$ such that every $F$-free graph $G$ with clique number $ω(G)$ has chromatic number at most $f(ω(G))$. Aboulker, Charbit, and Naserasr [Extension of Gyárfás-Sumner Conjecture to Digraphs; E-JC 2021] proposed an analogue of this conjecture to the dichromatic number of oriented graphs. The dichromatic number of a digraph $D$ is the minimum number of colors required to color the vertex set of $D$ so that no directed cycle in $D$ is monochromatic. Aboulker, Charbit, and Naserasr's $\overrightarrowχ$-boundedness conjecture states that for every oriented forest $F$, there is some function $f$ such that every $F$-free oriented graph $D$ has dichromatic number at most $f(ω(D))$, where $ω(D)$ is the size of a maximum clique in the graph underlying $D$. In this paper, we perform the first step towards proving Aboulker, Charbit, and Naserasr's $\overrightarrowχ$-boundedness conjecture by showing that it holds when $F$ is any orientation of a path on four vertices. |
| title | Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of $P_4$ |
| topic | Combinatorics Discrete Mathematics 05C15, 05C20, 05C38, 05C69 |
| url | https://arxiv.org/abs/2209.06171 |