서지주요정보
Hadwiger's conjecture and its variants = 하트비거의 추측과 그에 대한 변형
서명 / 저자 Hadwiger's conjecture and its variants = 하트비거의 추측과 그에 대한 변형 / Dong Yeap Kang.
발행사항 [대전 : 한국과학기술원, 2016].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8029054

소장위치/청구기호

학술문화관(문화관) 보존서고

MMAS 16005

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

Hadwiger's conjecture, which is one of the infamous conjectures in graph theory, states that for $t \geq 1$, every graph with no $K_t$ as a minor is (t-1)-colourable. Gerards and Seymour strengthened this conjecture, that every graph with no $K_t$ as an odd minor is (t-1)-colourable. We are interested in variants of both conjectures, in terms of an improper colouring: for $t \geq 1$, is there an integer D such that every graph G with no $K_t$ minor (odd minor) has a vertex partition into k(t) parts so that every subgraph induced on each partition has the maximum degree at most D? For graphs with no $K_t$ minor, Edwards, Kim, Oum, Seymour, and the author proved k(t) = t-1 for $t \geq 1$, and this is sharp. With the essentially same proof, this holds for graphs with no bipartite $K_t$ subdivision. For graphs with no odd $K_t$ -minor, Oum and the author proved k(t) = 7t - 10 for $t \geq 2$. Using some previous results, this improves the result by Kawarabayashi.

하트비거의 추측은 "4색 정리"를 확장하는 추측으로, $t \geq 1$ 에 대해서 $K_t$ minor가 없는 그래프는 t-1개의 색으로 칠할 수 있다는 추측입니다. Gerards와 Seymour는 이 추측을 강화하여, $t \geq 1$에 대해서 odd $K_t$ minor가 없는 그래프 또한 t-1개의 색으로 칠할 수 있다고 추측하였습니다. 저희의 연구는 하트비거의 추측을 improper colouring의 관점에서 보는 것에 관심이 있습니다: $t \geq 1$ 에 대해서, 어떤 D가 존재해서 $K_t$ minor가 없는 그래프 G의 정점 집합을 k(t)개의 서로소인 집합으로 분할했을 때, 각 집합에 대한 유도부분그래프(induced subgraph)의 최대 차수가 D 이내가 되게 할 수 있는가? $t \geq 1$ 에 대해서 $K_t$ minor가 없는 그래프에 대해서, Edwards, Kim, Oum, Seymour, 그리고 저자는 k(t) = t-1의 경우 성립함을 보였고, 이것이 최적임을 보였습니다. 유사한 방식으로, bipartite $K_t$ subdivision이 없는 그래프에 대해서도 이것이 성립합을 알 수 있습니다. $t \geq 2$ 에 대해서 odd $K_t$ minor가 없는 그래프에 대해서, Oum과 저자는 k(t) = 7t - 10의 경우 성립합을 보였습니다. 이를 이용하여, Kawarabayashi의 기존의 결과물을 개선할 수 있습니다.

서지기타정보

서지기타정보
청구기호 {MMAS 16005
형태사항 iii, 23 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 강동엽
지도교수의 영문표기 : Sang-il Oum
지도교수의 한글표기 : 엄상일
학위논문 학위논문(석사) - 한국과학기술원 : 수리과학과,
서지주기 References : p. 19-20
주제 hadwiger
coloring
minor
graph
odd minor
하트비거
채색
마이너
그래프
홀수 마이너
QR CODE qr code