اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدExtension of Gyarfas-Sumner conjecture to digraphs
151
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The dichromatic number of a digraph $D$ is the minimum number of colors needed to color its vertices in such a way that each color class induces an acyclic digraph. As it generalizes the notion of the chromatic number of graphs, it has been a recent center of study. In this work we look at possible extensions of Gyarfas-Sumner conjecture. More precisely, we propose as a conjecture a simple characterization of finite sets $mathcal F$ of digraphs such that every oriented graph with sufficiently large dichromatic number must contain a member of $mathcal F$ as an induce subdigraph. Among notable results, we prove that oriented triangle-free graphs without a directed path of length $3$ are $2$-colorable. If condition of triangle-free is replaced with $K_4$-free, then we have an upper bound of $414$. We also show that an orientation of complete multipartite graph with no directed triangle is 2-colorable. To prove these results we introduce the notion of emph{nice sets} that might be of independent interest.
قيم البحث
اقرأ أيضاً
We define strongly chordal digraphs, which generalize strongly chordal graphs and chordal bipartite graphs, and are included in the class of chordal digraphs. They correspond to square 0,1 matrices that admit a simultaneous row and column permutation
avoiding the {Gamma} matrix. In general, it is not clear if these digraphs can be recognized in polynomial time, and we focus on symmetric digraphs (i.e., graphs with possible loops), tournaments with possible loops, and balanced digraphs. In each of these cases we give a polynomial-time recognition algorithm and a forbidden induced subgraph characterization. We also discuss an algorithm for minimum general dominating set in strongly chordal graphs with possible loops, extending and unifying similar algorithms for strongly chordal graphs and chordal bipartite graphs.
We consider three graphs, $G_{7,3}$, $G_{7,4}$, and $G_{7,6}$, related to Kellers conjecture in dimension 7. The conjecture is false for this dimension if and only if at least one of the graphs contains a clique of size $2^7 = 128$. We present an aut
omated method to solve this conjecture by encoding the existence of such a clique as a propositional formula. We apply satisfiability solving combined with symmetry-breaking techniques to determine that no such clique exists. This result implies that every unit cube tiling of $mathbb{R}^7$ contains a facesharing pair of cubes. Since a faceshare-free unit cube tiling of $mathbb{R}^8$ exists (which we also verify), this completely resolves Kellers conjecture.
We prove a conjecture of Ohba which says that every graph $G$ on at most $2chi(G)+1$ vertices satisfies $chi_ell(G)=chi(G)$.
A celebrated result of Morse and Hedlund, stated in 1938, asserts that a sequence $x$ over a finite alphabet is ultimately periodic if and only if, for some $n$, the number of different factors of length $n$ appearing in $x$ is less than $n+1$. Attem
pts to extend this fundamental result, for example, to higher dimensions, have been considered during the last fifteen years. Let $dge 2$. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of $ZZ^d$ definable by a first order formula in the Presburger arithmetic $<ZZ;<,+>$. With this latter notion and using a powerful criterion due to Muchnik, we exhibit a complete extension of the Morse--Hedlund theorem to an arbitrary dimension $d$ and characterize sets of $ZZ^d$ definable in $<ZZ;<,+>$ in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.
Motivated by a hat guessing problem proposed by Iwasawa cite{Iwasawa10}, Butler and Graham cite{Butler11} made the following conjecture on the existence of certain way of marking the {em coordinate lines} in $[k]^n$: there exists a way to mark one po
int on each {em coordinate line} in $[k]^n$, so that every point in $[k]^n$ is marked exactly $a$ or $b$ times as long as the parameters $(a,b,n,k)$ satisfies that there are non-negative integers $s$ and $t$ such that $s+t = k^n$ and $as+bt = nk^{n-1}$. In this paper we prove this conjecture for any prime number $k$. Moreover, we prove the conjecture for the case when $a=0$ for general $k$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
