최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기The journal of the institute of internet, broadcasting and communication : JIIBC, v.14 no.5, 2014년, pp.263 - 269
In this paper, I disprove Hadwiger conjecture of the vertex coloring problem, which asserts that "All
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
핵심어 | 질문 | 논문에서 추출한 답변 |
---|---|---|
특별한 조건을 명시하지 않는 한 그래프 색칠 문제는 일반적으로 무엇을 의미하는가? | 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] |
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.
Ed. Pegg, Jr, "Graph Minor," http://mathworld.wolfram.com/Graph Minor.html, 2009.
Wikipedia, "Minor," http://en.wikipedia.org/wiki/Minor, Wikimedia Foundation Inc., 2014.
Wikipedia, "Independent Set Problem," http://en.wikipedia.org/wiki/Independent_set_problem, Wikimedia Foundation Inc., 2014.
Wikipedia, "Vertex Cover," http://en.wikipedia.org/wiki/Vertex_cover, Wikimedia Foundation Inc., 2014.
Wikipedia, "Degree (Graph Theory)," http://en.wikipedia.org/wiki/Degree_(graph-theory), Wikimedia Foundation Inc., 2014.
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
출판사/학술단체 등이 한시적으로 특별한 프로모션 또는 일정기간 경과 후 접근을 허용하여, 출판사/학술단체 등의 사이트에서 이용 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.