서지주요정보
Graph decompositions and related extremal problems = 그래프 분할과 관련된 극단 문제
서명 / 저자 Graph decompositions and related extremal problems = 그래프 분할과 관련된 극단 문제 / Dong Yeap Kang.
저자명 Kang, Dong Yeap ; 강동엽
발행사항 [대전 : 한국과학기술원, 2020].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8035436

소장위치/청구기호

학술문화관(도서관)2층 패컬티라운지(학위논문)

DMAS 20008

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

We present several results on graph decompositions and related extremal problems. The first result discusses the decomposition of graphs with no odd complete minor, the second result investigates how minor-monotone changes after adding a few random edges, and how the structure of a given graph changes after these random edge perturbations. The third and fourth results focus on directed graphs and their extremal properties, and study how many edges can be deleted while preserving the vertex/edge-connectivity of a given highly connected tournament-like digraph, or how a highly connected tournament-like digraph can be partitioned into many highly connected pieces with desired shapes. The last result is related to the rational exponent conjecture by Erdős and Simonovits in 1980s, which studies how many edges an $n$-vertex graph $G$ can have if $G$ does not contain a bipartite graph $H$ as a subgraph, and the exponents of these extremal functions.

이 논문에서는 그래프 분할과 그와 연관된 극단적 그래프 이론의 여러 결과들에 대해서 다루었다. 첫번째 결과는 완전그래프를 odd minor로 갖지 않는 그래프의 분할에 대한 결과이며, 두번째 결과는 그래프에 적은 수의 랜덤한 edge들을 추가하였을때 minor-monotone한 패러미터가 얼만큼 변하는지, 그리고 그 결과 기존의 그래프의 구조에 얼만큼 변화를 일으키는지에 대한 연구 결과이다. 세번째와 네번째 연구 결과는 방향그래프에 관한 극단적 그래프 이론의 결과들로, 잘 연결된 토너먼트에 가까운 방향그래프에서 얼만큼 많은 edge들을 제거하더라도 연결성을 유지할 수 있는지, 또는 그러한 방향그래프를 여러 개의 잘 연결된 원하는 형태를 갖는 부분방향그래프로 분할할 수 있는지에 관하여 연구하였다. 마지막으로, 다섯번째 결과는 1980년대 Erdős와 Simonovits의 rational exponent conjecture과 관련된 연구 결과로, 특정 이분그래프를 부분그래프로서 갖지 않는 $n$개의 정점을 갖는 그래프가 얼만큼 많은 edge를 가질 수 있고, 그리고 그 함수가 어떤 종류의 차수를 갖는지에 대하여 연구하였다.

서지기타정보

서지기타정보
청구기호 {DMAS 20008
형태사항 v, 145 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 강동엽
지도교수의 영문표기 : Sang-il Oum
지도교수의 한글표기 : 엄상일
수록잡지명 : "Improper colouring of graphs with no odd clique minor". COMBINATORICS PROBABILITY & COMPUTING, v.28.no.5, pp.740-754(2019)
수록잡지명 : "Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs". COMBINATORICS PROBABILITY & COMPUTING, v.28.no.3, pp.423-464(2019)
학위논문 학위논문(박사) - 한국과학기술원 : 수리과학과,
서지주기 References : p. 132-142
주제 Graph Decomposition
Extremal graph theory
Graph minor
Random graphs
Tournaments
Directed graphs
Four colour theorem
Chromatic number
Rational exponent conjecture
그래프 분할
극단 그래프 이론
그래프 마이너
랜덤 그래프
토너먼트
방향 그래프
4색 정리
채색수
유리수 차수 추측
QR CODE qr code