اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدProof of the Core Conjecture of Hilton and Zhao
72
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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$.
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 (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.
A typical decomposition question asks whether the edges of some graph $G$ can be partitioned into disjoint copies of another graph $H$. One of the oldest and best known conjectures in this area, posed by Ringel in 1963, concerns the decomposition of
complete graphs into edge-disjoint copies of a tree. It says that any tree with $n$ edges packs $2n+1$ times into the complete graph $K_{2n+1}$. In this paper, we prove this conjecture for large $n$.
In the context of the (generalized) Delta Conjecture and its compositional form, DAdderio, Iraci, and Wyngaerd recently stated a conjecture relating two symmetric function operators, $D_k$ and $Theta_k$. We prove this Theta Operator Conjecture, findi
ng it as a consequence of the five-term relation of Mellit and Garsia. As a result, we find surprising ways of writing the $D_k$ operators.
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)$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
