اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Core Conjecture of Hilton and Zhao I: Pseudo-multifan and Lollipop
97
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A simple graph $G$ with maximum degree $Delta$ is overfull if $|E(G)|>Delta lfloor |V(G)|/2rfloor$. The core of $G$, denoted $G_{Delta}$, is the subgraph of $G$ induced by its vertices of degree $Delta$. Clearly, the chromatic index of $G$ equals $Delta+1$ if $G$ is overfull. Conversely, Hilton and Zhao in 1996 conjectured that if $G$ is a simple connected graph with $Deltage 3$ and $Delta(G_Delta)le 2$, then $chi(G)=Delta+1$ implies that $G$ is overfull or $G=P^*$, where $P^*$ is obtained from the Petersen graph by deleting a vertex (Core Conjecture). The goal of this paper is to develop the concepts of pseudo-multifan and lollipop and study their properties in an edge colored graph. These concepts and properties are of independent interests, and will be particularly used to prove the Core Conjecture in a subsequent paper.
قيم البحث
اقرأ أيضاً
Let $G$ be a simple graph with maximum degree $Delta$. We call $G$ emph{overfull} if $|E(G)|>Delta lfloor |V(G)|/2rfloor$. The emph{core} of $G$, denoted $G_{Delta}$, is the subgraph of $G$ induced by its vertices of degree $Delta$. A classic result
of Vizing shows that $chi(G)$, the chromatic index of $G$, is either $Delta$ or $Delta+1$. It is NP-complete to determine the chromatic index for a general graph. However, if $G$ is overfull then $chi(G)=Delta+1$. Hilton and Zhao in 1996 conjectured that if $G$ is a simple connected graph with $Deltage 3$ and $Delta(G_Delta)le 2$, then $chi(G)=Delta+1$ if and only if $G$ is overfull or $G=P^*$, where $P^*$ is obtained from the Petersen graph by deleting a vertex. This conjecture, if true, implies an easy approach for calculating $chi(G)$ for graphs $G$ satisfying the conditions. The progress on the conjecture has been slow: it was only confirmed for $Delta=3,4$, respectively, in 2003 and 2017. In this paper, we confirm this conjecture for all $Deltage 4$.
A simple graph $G$ with maximum degree $Delta$ is overfull if $|E(G)|>Delta lfloor |V(G)|/2rfloor$. The core of $G$, denoted $G_{Delta}$, is the subgraph of $G$ induced by its vertices of degree $Delta$. Clearly, the chromatic index of $G$ equals $De
lta+1$ if $G$ is overfull. Conversely, Hilton and Zhao in 1996 conjectured that if $G$ is a simple connected graph with $Deltage 3$ and $Delta(G_Delta)le 2$, then $chi(G)=Delta+1$ implies that $G$ is overfull or $G=P^*$, where $P^*$ is obtained from the Petersen graph by deleting a vertex. Cariolaro and Cariolaro settled the base case $Delta=3$ in 2003, and Cranston and Rabern proved the next case $Delta=4$ in 2019. In this paper, we give a proof of this conjecture for all $Deltage 4$.
Babson and Steingr{i}msson introduced generalized permutation patterns and showed that most of the Mahonian statistics in the literature can be expressed by the combination of generalized pattern functions. Particularly, they defined a new Mahonian s
tatistic in terms of generalized pattern functions, which is denoted $stat$. Given a permutation $pi$, let $des(pi)$ denote the descent number of $pi$ and $maj(pi)$ denote the major index of $pi$. Babson and Steingr{i}msson conjectured that $(des,stat)$ and $(des,maj)$ are equidistributed on $S_n$. Foata and Zeilberger settled this conjecture using q-enumeration, generating functions and Maple packages ROTA and PERCY. Later, Burstein provided a bijective proof of a refinement of this conjecture. In this paper, we give a new bijective proof of this conjecture.
Let $m$, $n$, and $k$ be integers satisfying $0 < k leq n < 2k leq m$. A family of sets $mathcal{F}$ is called an $(m,n,k)$-intersecting family if $binom{[n]}{k} subseteq mathcal{F} subseteq binom{[m]}{k}$ and any pair of members of $mathcal{F}$ have
nonempty intersection. Maximum $(m,k,k)$- and $(m,k+1,k)$-intersecting families are determined by the theorems of ErdH{o}s-Ko-Rado and Hilton-Milner, respectively. We determine the maximum families for the cases $n = 2k-1, 2k-2, 2k-3$, and $m$ sufficiently large.
A conjecture of Graver from 1991 states that the generic $3$-dimensional rigidity matroid is the unique maximal abstract $3$-rigidity matroid with respect to the weak order on matroids. Based on a close similarity between the generic $d$-dimensional
rigidity matroid and the generic $C_{d-2}^{d-1}$-cofactor matroid from approximation theory, Whiteley made an analogous conjecture in 1996 that the generic $C_{d-2}^{d-1}$-cofactor matroid is the unique maximal abstract $d$-rigidity matroid for all $dgeq 2$. We verify the case $d=3$ of Whiteleys conjecture in this paper. A key step in our proof is to verify a second conjecture of Whiteley that the `double V-replacement operation preserves independence in the generic $C_2^1$-cofactor matroid.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
