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의 기존의 결과물을 개선할 수 있습니다.
