엄상일 연구실

본 논문은 평면 그래프 마이너를 제외하는 그래프의 트리너비에 대한 선형 상한을 연구합니다. 평면 그래프 H에 대해 H를 마이너로 포함하지 않는 그래프의 트리너비 상한 f(H)를 분석하며, 특히 정점-분리 사이클의 개수와의 관계를 규명합니다. 유계 성분 크기를 가진 평면 그래프 클래스에서 정점-분리 사이클 개수가 O(n/log n) 이하일 때 f(H)가 선형임을 보이고, r개 사이클의 분리 합집합에 대해 f(H) ≤ n + O(√n) (r=2일 때)의 개선된 상한을 제시합니다.

본 연구는 기본 그래프에 무작위 간선을 추가할 때 마이너-단조 그래프 매개변수가 얼마나 증가하는지 정량적으로 분석합니다. 연결 그래프에 소수의 무작위 간선만 추가해도 결과 그래프의 트리-너비, 종수, 하드위거 수가 기본 그래프의 구조와 무관하게 매우 커짐을 보입니다.

본 논문은 1965년 Erdős-Pósa 정리를 일반화하여 사이클 패킹과 사이클을 제거하는 최소 정점 집합 사이의 이중성을 특성화합니다. 길이가 z modulo ℓ인 사이클에 대해 이중성이 성립하는 모든 정수 쌍 (ℓ, z)을 규명하고, 이를 유한개의 아벨군으로 표지된 그래프의 사이클로 일반화합니다. 이 결과는 알려진 사이클 유형들을 통합하며 새로운 결과를 제공합니다.