Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Hadwiger Conjecture
227
0
0.0
(
0
)
Authors
Dhananjay P. Mehendale
Ask ChatGPT about the research
No Arabic abstract
We propose an algorithm to reduce a k-chromatic graph to a complete graph of largest possible order through a well defined sequence of contractions. We introduce a new matrix called transparency matrix and state its properties. We then define correct contraction procedure to be executed to get largest possible complete graph from given connected graph. We finally give a characterization for k-chromatic graphs and use it to settle Hadwigers conjecture.
rate research
Read More
Hadwiger Conjecture has been an open problem for over a half century1,6, which says that there is at most a complete graph Kt but no Kt+1 for every t-colorable graph. A few cases of Hadwiger Conjecture, such as 1, 2, 3, 4, 5, 6-colorable graphs have been completely proved to convince all1-5, but the proofs are tremendously difficult for over the 5-colorable graph6,7. Although the development of graph theory inspires scientists to understand graph coloring deeply, it is still an open problem for over 7-colorable graphs6,7. Therefore, we put forward a brand new chromatic graph configuration and show how to describe the graph coloring issues in chromatic space. Based on this idea, we define a chromatic plane and configure the chromatic coordinates in Euler space. Also, we find a method to prove Hadwiger Conjecture for every 8-coloring graph feasible.
We define new natural variants of the notions of weighted covering and separation numbers and discuss them in detail. We prove a strong duality relation between weighted covering and separation numbers and prove a few relations between the classical and weighted covering numbers, some of which hold true without convexity assumptions and for general metric spaces. As a consequence, together with some volume bounds that we discuss, we provide a bound for the famous Levi-Hadwiger problem concerning covering a convex body by homothetic slightly smaller copies of itself, in the case of centrally symmetric convex bodies, which is qualitatively the same as the best currently known bound. We also introduce the weighted notion of the Levi-Hadwiger covering problem, and settle the centrally-symmetric case, thus also confirm Nasz{o}dis equivalent fractional illumination conjecture in the case of centrally symmetric convex bodies (including the characterization of the equality case, which was unknown so far).
We show that we cannot avoid the existence of at least one directed circuit of length less than or equal to (n/r) in a digraph on n vertices with out-degree greater than or equal to r. This is well-known Caccetta-Haggkvist problem.
We settle the Path Decomposition Conjecture (P.D.C.) due to Tibor Gallai for minimally connected graphs, i.e. trees. We use this validity for trees and settle the P. D. C. using induction on the number of edges for all connected graphs. We then obtain a new bound for the number of paths in a path cover in terms of the number of edges using idea of associating a tree with a connected graph. We then make use of a spanning tree in the given connected graph and its associated basic path cover to settle the conjecture of Tibor Gallai in an alternative way. Finally, we show the existence of Hamiltonian path cover satisfying Gallai bound for complete graphs of even order and discuss some of its possible ramifications.
Let $lambda(m)$ be the $m$th coefficient of a modular form $f(z)=sum_{mgeq 1} lambda(m)q^m$ of weight $kgeq 4$, let $p^n$ be a prime power, and let $varepsilon>0$ be a small number. An approximate of the Atkin-Serre conjecture on the lower bound of the form $left |lambdaleft (p^nright )right | geq p^{(k-1)n/2-2k+2varepsilon}$ is presented in this note.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
