(P6, triangle)-free digraphs have bounded dichromatic number [PDF]
, 2022 9 pages. Thie version corrects some mistakes on page 2 in the introduction, we were incorrectly citing some of the previous papers on the ...
P Aboulker +3 more
openalex +3 more sources
Dichromatic number, circulant tournaments and Zykov sums of digraphs [PDF]
Discussiones Mathematicae Graph Theory, 2000 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Vı́ctor Neumann-Lara
openalex +2 more sources
Minimum Acyclic Number and Maximum Dichromatic Number of Oriented Triangle-Free Graphs of a Given Order [PDF]
The Electronic Journal of CombinatoricsLet $D$ be a digraph. Its acyclic number $\vec{\alpha}(D)$ is the maximum order of an acyclic induced subdigraph and its dichromatic number $\vec{\chi}(D)$ is the least integer $k$ such that $V(D)$ can be partitioned into $k$ subsets inducing acyclic subdigraphs.
Pierre Aboulker +3 more
+6 more sources
Subdivisions in Digraphs of Large Out-Degree or Large Dichromatic Number [PDF]
The Electronic Journal of Combinatorics, 2019 In 1985, Mader conjectured the existence of a function $f$ such that every digraph with minimum out-degree at least $f(k)$ contains a subdivision of the transitive tournament of order $k$. This conjecture is still completely open, as the existence of $f(5)$ remains unknown.
Pierre Aboulker +5 more
openalex +9 more sources
Cycle reversions and dichromatic number in tournaments [PDF]
European Journal of Combinatorics, 2018 We show that if $D$ is a tournament of arbitrary size then $D$ has finite strong components after reversing a locally finite sequence of cycles. In turn, we prove that any tournament can be covered by two acyclic sets after reversing a locally finite sequence of cycles. This provides a partial solution to a conjecture of S. Thomass .
P.J. Ellis, Dániel T. Soukup
openalex +6 more sources
Reducing the dichromatic number via cycle reversions in infinite digraphs
European Journal of Combinatorics, 2020 19 ...
P.J. Ellis +2 more
openalex +3 more sources
($\overrightarrow{P_6}$, triangle)-Free Digraphs Have Bounded Dichromatic Number [PDF]
The Electronic Journal of CombinatoricsThe dichromatic number of an oriented graph is the minimum size of a partition of its vertices into acyclic induced subdigraphs. We prove that oriented graphs with no induced directed path on six vertices and no triangle have bounded dichromatic number. This is one (small) step towards the general conjecture asserting that for every oriented tree
P Aboulker +3 more
openalex +3 more sources
A Simple Construction of Tournaments with Finite and Uncountable Dichromatic Number [PDF]
The dichromatic number $\chi(\vec{G})$ of a digraph $\vec{G}$ is the minimum number of colors needed to color the vertices $V(\vec{G})$ in such a way that no monochromatic directed cycle is obtained. In this note, for any $k\in \mathbb{N}$, we give a simple construction of tournaments with dichromatic number exactly equal to $k$.
Arpan Sadhukhan
openalex +3 more sources
Advancements and limitations of image-enhanced endoscopy in colorectal lesion diagnosis and treatment selection: A narrative review. [PDF]
DEN OpenAbstract Colorectal cancer (CRC) is a leading cause of cancer‐related mortality, highlighting the need for early detection and accurate lesion characterization. Traditional white‐light imaging has limitations in detecting lesions, particularly those with flat morphology or minimal color contrast with the surrounding mucosa.
Sakamoto T +3 more
europepmc +2 more sources
Acyclic dichromatic number of oriented graphs [PDF]
The dichromatic number $\vecχ(D)$ of a digraph $D=(V,A)$ is the minimum number of sets in a partition $V_1,\ldots{},V_k$ of $V$ into $k$ subsets so that the induced subdigraph $D[V_i]$ is acyclic for each $i\in [k]$. This is a generalization of the chromatic number for undirected graphs as a graph has chromatic number at most $k$ if and only if the ...
Jørgen Bang‐Jensen +2 more
openalex +3 more sources