Disproof of Hadwiger Conjecture

In this paper, I disprove Hadwiger conjecture of the vertex coloring problem, which asserts that “All Kk-minor free graphs can be colored with k-1 number of colors, i.e., X(G) = k given Kk-minor.” Pursuant to Hadwiger conjecture, one shall obtain an NP-complete k-minor to determine X(G) = k, and solve another NP-complete vertex coloring problem as a means to color vertices. In order to disprove Hadwiger conjecture in this paper, I propose an algorithm of linear time complexity O(V) that yields the exact solution to the vertex coloring problem. The proposed algorithm assigns vertex with the minimum degree to the Maximum Independent Set (MIS) and repeats this process on a simplified graph derived by deleting adjacent edges to the MIS vertex so as to finally obtain an MIS with a single color. Next, it repeats the process on a simplified graph derived by deleting edges of the MIS vertex to obtain an MIS whose number of vertex color corresponds to X(G) = k. Also presented in this paper using the proposed algorithm is an additional algorithm that searches solution of X″(G), the total chromatic number, which also remains NP-complete. When applied to a NP-minor graph, the proposed algorithm has obtained X(G) = 3 instead of X(G) = 4, proving that the Hadwiger conjecture is not universally applicable to all the graphs. The proposed algorithm, however, is a simple algorithm that directly obtains an independent set minor of X(G) = k to assign an equal color to the vertices of each independent set without having to determine minors in the first place.