Study on structures of digraphs and graphs in the aspect of their holes

국문 초록 (Abstract)

이 논문에서는 유향그래프와 그래프의 홀의 관점에서 계통발생 그래프와 그래프의 삼각화에 대하여 연구한다.
길이 4 이상인 유도된 싸이클을 홀이라 하고 홀이 없는 그래프를 삼각화된 그래프라 한다. 구체적으로, 싸이클을 갖지 않는 유향그래프의 계통발생 그래프가 삼각화된 그래프인지 판정하고, 주어진 그래프를 삼각화하여 클릭수가 크게 차이 나지 않는 그래프를 만드는 방법을 찾고자 한다. 이 논문은 연구 내용에 따라 두 부분으로 나뉜다.

먼저 $(1, i)$ 유향그래프와 $(i, 1)$ 유향그래프의 계통발생 그래프를 완전하게 특징화하고, $(2, j)$ 유향그래프 $D$의 모든 유향변에서 방향을 제거한 그래프가 삼각화된 그래프이면, $D$의 계통발생 그래프 역시 삼각화된 그래프임을 보였다. 또한 적은 수의 삼각형을 갖는 연결된 그래프의 계통발생수를 계산한 정리를 확장하여 많은 수의 삼각형을 포함한 연결된 그래프의 계통발생수를 계산하였다.

다른 한 편 그래프 $G$의 비삼각화 지수 $i(G)$에 대하여 $\omega(G^*)-\omega(G) \le i(G)$를 만족하는 $G$의 삼각화된 그래프 $G^*$가 존재함을 보였다.
그리고 이를 도구로 이용하여 NC property를 만족하는 그래프가 Hadwiger 추측과 Erd\H{o}s-Faber-Lov\'{a}sz 추측을 만족함을 증명하고, 비삼각화 지수가 유계인 그래프들이 linearly $\chi$-bounded임을 증명하였다.

다국어 초록 (Multilingual Abstract)

This thesis aims at studying phylogeny graphs and graph completions in the aspect of holes of graphs or digraphs. A hole of a graph is an induced cycle of length at least four and a graph is chordal if it does not contain a hole. Specifically, we determine whether the phylogeny graphs of acyclic digraphs are chordal or not and find a way of chordalizing a graph without increasing the size of maximum clique not so much. In this vein, the thesis is divided into two parts.

In the first part, we completely characterize phylogeny graphs of $(1, i)$ digraphs and $(i,1)$ digraphs, respectively, for a positive integer $i$. Then, we show that the phylogeny graph of a $(2,j)$ digraph $D$ is chordal if the underlying graph of $D$ is chordal for any positive integer $j$. In addition, we extend the existing theorems computing phylogeny numbers of connected graph with a small number of triangles to results computing phylogeny numbers of connected graphs with many triangles.

In the second part, we present a minimal chordal supergraph $G^*$ of a graph $G$ satisfying the inequality $\omega(G^*) - \omega(G) \le i(G)$ for the non-chordality index $i(G)$ of $G$. Using the above chordal supergraph as a tool, we prove that the family of graphs satisfying the NC property satisfies the Hadwiger conjecture and the Erd\H{o}s-Faber-Lov\'{a}sz Conjecture, and the family of graphs with bounded non-chordality indices is linearly $\chi$-bounded.

목차 (Table of Contents)

• Contents
• Abstract i
• 1 Introduction 1
• 1.1 Basic notions . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
• 1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
• 1.2.1 Phylogeny graphs . . . . . . . . . . . . . . . . . . . . . 8
• 1.2.2 Graph colorings and chordal completions . . . . . . . . 14
• 2 Phylogeny graphs 19
• 2.1 Chordal phylogeny graphs . . . . . . . . . . . . . . . . . . . . 19
• 2.1.1 (1,j) phylogeny graphs and (i,1) phylogeny graphs . . 20
• 2.1.2 (2,j) phylogeny graphs . . . . . . . . . . . . . . . . . . 28
• 2.2 The phylogeny number and the triangles and the diamonds of
• a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
• 3 A new minimal chordal completion 61
• 3.1 Graphs with the NC property . . . . . . . . . . . . . . . . . . 64
• 3.2 The Erd˝ os-Faber-Lovász Conjecture . . . . . . . . . . . . . . . 73
• 3.3 A minimal chordal completion of a graph . . . . . . . . . . . . 80
• 3.3.1 Non-chordality indices of graphs . . . . . . . . . . . . . 80
• 3.3.2 Making a local chordalization really local . . . . . . . . 89
• 3.4 New χ-bounded classes . . . . . . . . . . . . . . . . . . . . . . 97
• Abstract (in Korean) 107