Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProof of the Core Conjecture of Hilton and Zhao
72
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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. 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 $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.
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, finding 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)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
