본 논문은 지금까지 미해결 문제로 알려진 정점 색칠 문제에 대한 Hadwiger 추측의 반증을 제시하였다. Hadwiger 추측은 "모든 $K_k$-minor free 그래프는 k-1개의 색으로 칠할 수 있다. 즉, $K_k$-마이너를 얻으면 ${\chi}(G)=k$이다." Hadwiger 추측을 적용하여 정점 색칠을 할 경우, 먼저 NP-완전 (NP-complete)인 $K_k$-마이너를 구하여 ${\chi}(G)=k$를 결정하고, 다시 NP-완전인 정점 색칠 문제를 풀어야 한다. Hadwiger 추측을 반증하기 위해 본 논문은 정점 색칠의 정확한 해를 O(V)의 선형시간으로 구하는 알고리즘을 제시하였다. 제안된 알고리즘은 그래프의 최소 차수를 가진 정점을 최대독립집합 (MIS)으로 하고, MIS 정점의 인접 정점 간선을 삭제한 축소된 그래프에 대해 이 과정을 반복하면서 하나의 색을 가진 MIS를 얻는다. 다음으로 MIS 정점의 간선을 삭제한 축소된 그래프에 대해 동일한 과정을 수행하여 MIS의 개수가 정점 채색수${\chi}(G)=k$가 되는 해를 얻는다. 제안된 알고리즘을 적용하여 NP-완전 문제인 완전 색칠 (total coloring) 채색수 ${\chi}^{{\prime}{\prime}}(G)$의 해를 구하는 알고리즘을 제안하였다. 제안된 알고리즘을 $K_4$-마이너 그래프에 적용한 결과 ${\chi}(G)=4$가 아닌 ${\chi}(G)=3$을 얻었다. 결국, Hadwiger 추측은 모든 그래프에 대해 적용되지 않음을 알 수 있다. 제안된 알고리즘은 마이너를 구하지 않으며, 주어진 그래프에 대해 직접 ${\chi}(G)=k$인 독립집합 마이너를 구하여 각 독립집합 정점들에 동일한 색을 배정하는 단순한 방법이다.
본 논문은 지금까지 미해결 문제로 알려진 정점 색칠 문제에 대한 Hadwiger 추측의 반증을 제시하였다. Hadwiger 추측은 "모든 $K_k$-minor free 그래프는 k-1개의 색으로 칠할 수 있다. 즉, $K_k$-마이너를 얻으면 ${\chi}(G)=k$이다." Hadwiger 추측을 적용하여 정점 색칠을 할 경우, 먼저 NP-완전 (NP-complete)인 $K_k$-마이너를 구하여 ${\chi}(G)=k$를 결정하고, 다시 NP-완전인 정점 색칠 문제를 풀어야 한다. Hadwiger 추측을 반증하기 위해 본 논문은 정점 색칠의 정확한 해를 O(V)의 선형시간으로 구하는 알고리즘을 제시하였다. 제안된 알고리즘은 그래프의 최소 차수를 가진 정점을 최대독립집합 (MIS)으로 하고, MIS 정점의 인접 정점 간선을 삭제한 축소된 그래프에 대해 이 과정을 반복하면서 하나의 색을 가진 MIS를 얻는다. 다음으로 MIS 정점의 간선을 삭제한 축소된 그래프에 대해 동일한 과정을 수행하여 MIS의 개수가 정점 채색수 ${\chi}(G)=k$가 되는 해를 얻는다. 제안된 알고리즘을 적용하여 NP-완전 문제인 완전 색칠 (total coloring) 채색수 ${\chi}^{{\prime}{\prime}}(G)$의 해를 구하는 알고리즘을 제안하였다. 제안된 알고리즘을 $K_4$-마이너 그래프에 적용한 결과 ${\chi}(G)=4$가 아닌 ${\chi}(G)=3$을 얻었다. 결국, Hadwiger 추측은 모든 그래프에 대해 적용되지 않음을 알 수 있다. 제안된 알고리즘은 마이너를 구하지 않으며, 주어진 그래프에 대해 직접 ${\chi}(G)=k$인 독립집합 마이너를 구하여 각 독립집합 정점들에 동일한 색을 배정하는 단순한 방법이다.
In this paper, I disprove Hadwiger conjecture of the vertex coloring problem, which asserts that "All $K_k$-minor free graphs can be colored with k-1 number of colors, i.e., ${\chi}(G)=k$ given $K_k$-minor." Pursuant to Hadwiger conjecture, one shall obtain an NP-com...
In this paper, I disprove Hadwiger conjecture of the vertex coloring problem, which asserts that "All $K_k$-minor free graphs can be colored with k-1 number of colors, i.e., ${\chi}(G)=k$ given $K_k$-minor." Pursuant to Hadwiger conjecture, one shall obtain an NP-complete k-minor to determine ${\chi}(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 ${\chi}(G)=k$. Also presented in this paper using the proposed algorithm is an additional algorithm that searches solution of ${\chi}^{{\prime}{\prime}}(G)$, the total chromatic number, which also remains NP-complete. When applied to a $K_4$-minor graph, the proposed algorithm has obtained ${\chi}(G)=3$ instead of ${\chi}(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 ${\chi}(G)=k$ to assign an equal color to the vertices of each independent set without having to determine minors in the first place.
In this paper, I disprove Hadwiger conjecture of the vertex coloring problem, which asserts that "All $K_k$-minor free graphs can be colored with k-1 number of colors, i.e., ${\chi}(G)=k$ given $K_k$-minor." Pursuant to Hadwiger conjecture, one shall obtain an NP-complete k-minor to determine ${\chi}(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 ${\chi}(G)=k$. Also presented in this paper using the proposed algorithm is an additional algorithm that searches solution of ${\chi}^{{\prime}{\prime}}(G)$, the total chromatic number, which also remains NP-complete. When applied to a $K_4$-minor graph, the proposed algorithm has obtained ${\chi}(G)=3$ instead of ${\chi}(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 ${\chi}(G)=k$ to assign an equal color to the vertices of each independent set without having to determine minors in the first place.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
제안 방법
Hadwiger 추측을 반증하기 위해 독립집합 개념을 적용하여 선형시간으로 Χ(G) = k의 정확한 해를 구하는 알고리즘을 제안하였다.
반면에 제안된 알고리즘은 O(V)회 수행으로 Χ(G) = k개의 독립집합을 구하였으며, 각 독립집합에 동일한 색이 이미 배정되어 추가적인 색 배정 알고리즘이 요구되지 않는다.
본 장에서는 그래프의 인접 정점들을 다른 색으로 색칠하는데 요구되는 최소의 채색수를 찾는 다항시간 알고리즘을 제안한다. 제안된 알고리즘은 최소 정점 피복 (minimum vertex cover, MVC)과 최대 독립집합 (maximum independent set, MIS) 개념을 적용한다.
그림 3은 Wikipedia[6]가 Hadwiger 추측을 설명하기 위해 제시한 그래프이다. 이 그래프를 대상으로 Hadwiger 추측을 적용하여 정점 색칠 방법을 살펴보고 문제점을 고찰한다.
제안된 알고리즘은 그래프의 최소 차수를 가진 정점을 MIS로, MIS 정점의 인접 정점을 MVC에 포함시키고 MVC 정점의 부속 간선을 모두 삭제한다. 이 결과 축소된 그래프에 대해 정점이 존재하지 않을 때까지 이 과정을 반복 수행하면 하나의 색을 배정할 수 있는 MIS 집합을 얻는다.
본 장에서는 그래프의 인접 정점들을 다른 색으로 색칠하는데 요구되는 최소의 채색수를 찾는 다항시간 알고리즘을 제안한다. 제안된 알고리즘은 최소 정점 피복 (minimum vertex cover, MVC)과 최대 독립집합 (maximum independent set, MIS) 개념을 적용한다.[14,15] 또한, MIS와 MVC를 찾기 위해 그래프의 차수 (degree, dG(v)) 개념을 적용한다.
성능/효과
(2) 모든 Kk-minor free 그래프는 k-1색칠이 가능하다.[5,8]
(3) Hadwiger 추측은 반드시 Kk-마이너가 존재하지 않으면 k-1개의 색으로 칠할 수 있다는 것이다. 반면에, 정점 색칠 문제는 최소의 채색수를 찾는 것이 목표이다.
(3) 모든 정수 t ≥ 1에 대해, 만약 그래프 G가 Kk + 1과 동형사상 (isomorphic)인 마이너를 가지지 않으면 k-색칠을 할 수 있다.
결국, 그래프의 정점을 색칠할 때, Hadwiger 추측에 기반하여 NP-완전인 간선 축약 과정을 거쳐 Kk-마이너를 얻고[6,12], 다시 k-1개의 색을 다시 칠하는 NP-완전 문제[1]를 해결할 필요가 없이 제안된 알고리즘을 적용하면 정확한 정점 색칠의 해를 선형시간 복잡도로 구할 수 있다.
Hadwiger 추측을 반증하기 위해 독립집합 개념을 적용하여 선형시간으로 Χ(G) = k의 정확한 해를 구하는 알고리즘을 제안하였다. 제안된 독립집합 정점 색칠 알고리즘을 적용하여 실험 그래프에 대해 색을 칠한 결과 K5-minor free 그래프는 k-1 = 4가 아닌 k-2 = 3인 결과를 얻었다.
질의응답
핵심어
질문
논문에서 추출한 답변
특별한 조건을 명시하지 않는 한 그래프 색칠 문제는 일반적으로 무엇을 의미하는가?
n개의 정점 (vertices, v)과 m개의 간선 (edges, e)으로 구성된 무방향 그래프 (undirected graph) G= (V,E), u,v∈V,e = {u,v}∈E에 대해, 색칠 문제 (coloring problem)는 정점 색칠 (vertex coloring, VC), 간선 색칠 (edge coloring, EC)과 완전 색칠 (total coloring, TC) 문제로 분류된다.[1-3] 특별한 조건을 명시하지 않는 한 그래프 색칠 문제는 일반적으로 정점 색칠을 의미한다.[1]
Hadwiger 추측은 무엇인가?
간선이 교차되지 않는 평면 그래프 (planar graph)에 대한 대표적인 이론으로 (G) ≤ 4인 4-색 이론 (four-color theorem)이 있다.[4,5] 또한, 주어진 그래프의 임의의 간선 {x,y}을 축약 (간선 양 끝단 2개 정점을 1개정점으로 병합하여 하나의 정점으로 만든다.)할 경우, 그래프의 Kk 완전 그래프 (complete graph)인 Kk-마이너 부분 그래프 (minor subgraph)를 얻을 수 있다.[6,7] 이때 Kk + 1-마이너 그래프가 되지 않으면 주어진 그래프는 k 개의 색으로 칠할 수 있다. 이 이론을 Hadwiger 추측 (conjecture)이라 하며, 수학분야에서 k+1≤6까지는 증명되었으나 k+1≥7인 그래프에 대해서는 증명되지 않은 미해결 문제로 남아 있다.
정점 색칠 문제는 무엇인가?
정점 색칠 문제는 동일 간선을 공유하는 인접 (adjacent) 정점들 (하나의 정점에 부속된 간선으로 연결된 모든 인접 정점들)간에는 다른 색을 할당하여 모든 정점들을 색칠하는데 요구되는 최소의 채색 수 (chromatic number) (G) = k를 찾는 문제이다.[1]
참고문헌 (16)
Wikipedia, "Graph Coloring," http://en.wikipedia.org/wiki/Graph_Coloring, Wikimedia Foundation Inc., 2014.
Wikipedia, "Edge Coloring," http://en.wikipedia.org/wiki/Edge_coloring, Wikimedia Foundation Inc., 2014.
Wikipedia, "Total Coloring," http://en.wikipedia.org/wiki/Total_coloring, Wikimedia Foundation Inc., 2014.
Wikipedia, "Four Color Theorem," http://en.wikipedia.org/wiki/Four_color_theorem, Wikimedia Foundation Inc., 2014.
B. Mohar, "What is a Graph Minor," Notices of the AMS, Vol. 53, No. 3, pp. 338-339, 2006.
Wikipedia, "Hadwiger Conjecture (Graph Theory)," http://en.wikipedia.org/wiki/Hadwiger_conjecture(graph_theory), Wikimedia Foundation Inc., 2014.
R. Naserasr and Y. Nigussie, "On a new Reformulation of Hadwiger Conjecture," Journal of Discrete Mathematics, Vol. 306, No. 23. pp. 3136-3139, Dec. 2006.
M. O. Albertson and J. P. Hutchinson, "Graph Color Extensions: When Hadwiger's Conjecture and Embeddings Help," The Electronic Journal of Combinatorics, Vol. 9, No. 1, pp. 1-10, Jan. 2002.
T. J. Hetherington and D. R. Woodall, "Edge and Total Choosability of Near-outerplanar Graphs," The Electronic Journal of Combinatorics, Vol. 13, No. 1, pp. 1-7, Jan. 2006.
G. Istrate, "On Hadwiger's Number of a Graph with Partial Information," Applied Mathematics Letters, Vol. Vol. 22, No. 2, pp. 1-7, Feb. 2009.
B. Reed and R. Thomas, "Clique Minors in Graphs and Their Complements," Journal of Combinatorial Theory Series B., Vol. 78, No. 1, pp. 81-85, Jan. 2000.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.