Zobrazeno 1 - 10
of 39
pro vyhledávání: '"05C20, 05C15"'
Autor:
Krone, Maximilian
A cut in a digraph $D=(V,A)$ is a set of arcs $\{uv \in A: u\in U, v\notin U\}$, for some $U\subseteq V$. It is known that the arc set $A$ is covered by $k$ cuts if and only if it admits a $k$-coloring such that no two consecutive arcs $uv, vw$ recei
Externí odkaz:
http://arxiv.org/abs/2410.06899
Autor:
Sadhukhan, Arpan
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
Externí odkaz:
http://arxiv.org/abs/2401.00829
The dichromatic number of a digraph $D$ is the minimum number of colors of a vertex coloring of $D$ such that $D$ has no monochromatic cycles. The Haj\'os join were recently extended to digraphs (using the dichromatic number) by J. Bang-Jensen et. al
Externí odkaz:
http://arxiv.org/abs/2301.07181
Autor:
Hompe, Patrick, Huynh, Tony
In 2017, Aharoni proposed the following generalization of the Caccetta-H\"{a}ggkvist conjecture: if $G$ is a simple $n$-vertex edge-colored graph with $n$ color classes of size at least $r$, then $G$ contains a rainbow cycle of length at most $\lceil
Externí odkaz:
http://arxiv.org/abs/2212.05697
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, vol. 25:1, Discrete Algorithms (March 1, 2023) dmtcs:10189
In 2020 Bang-Jensen et. al. generalized the Haj\'os join of two graphs to the class of digraphs and generalized several results for vertex colorings in digraphs. Although, as a consequence of these results, a digraph can be obtained by Haj\'os constr
Externí odkaz:
http://arxiv.org/abs/2210.05080
Autor:
Dochtermann, Anton, Singh, Anurag
Publikováno v:
European J. Combin. 110 (2023)
The neighborhood complex of a graph was introduced by Lov\'asz to provide topological lower bounds on chromatic number. More general homomorphism complexes of graphs were further studied by Babson and Kozlov. Such `Hom complexes' are also related to
Externí odkaz:
http://arxiv.org/abs/2108.10948
For a fixed simple digraph $F$ and a given simple digraph $D$, an $F$-free $k$-coloring of $D$ is a vertex-coloring in which no induced copy of $F$ in $D$ is monochromatic. We study the complexity of deciding for fixed $F$ and $k$ whether a given sim
Externí odkaz:
http://arxiv.org/abs/2102.07705
Generalizing well-known results of Erd\H{o}s and Lov\'asz, we show that every graph $G$ contains a spanning $k$-partite subgraph $H$ with $\lambda{}(H)\geq \lceil{}\frac{k-1}{k}\lambda{}(G)\rceil$, where $\lambda{}(G)$ is the edge-connectivity of $G$
Externí odkaz:
http://arxiv.org/abs/2008.05272
Reed showed that, if two graphs are $P_4$-isomorphic, then either both are perfect or none of them is. In this note we will derive an analogous result for perfect digraphs.
Comment: 5 pages, 1 figure
Comment: 5 pages, 1 figure
Externí odkaz:
http://arxiv.org/abs/1906.05650
Autor:
Cary, Michael
In this paper we prove that the dominator chromatic number of every oriented tree is invariant under reversal of orientation. In addition to this marquee result, we also prove the exact dominator chromatic number for arborescences and anti-arborescen
Externí odkaz:
http://arxiv.org/abs/1904.06293