On interval edge-coloring problem in hypergraphs

다국어 초록 (Multilingual Abstract)

An (proper) \textit{edge coloring} of a graph $G$ is a function $f:E(G)\rightarrow \mathbb{Z}$ so that no two edges sharing an end have the same value. A graph $G$ is \textit{interval edge-colorable} if there is an edge coloring of $G$ such that for any vertex of $G$, the colors of edges incident to the vertex are consecutive.
This notion was introduced by Asratian and Kamalian in 1987, in a relation to a scheduling problem. And it has been intensively studied by many researchers, especially focused on a problem to determine if given bipartite graph is interval edge-colorable or not.

In this thesis, we introduce an interval edge-coloring problem of a hypergraph and study its basic properties. We also give a necessary and sufficient condition for an $(n+1,n+1,n)$-regular tripartite 3-uniform hypergraph being interval $2n$-colorable.
Additionally, we find some interval edge-colorable bipartite graphs, in a relation of the question by Petrosyan and Khachatrian (2014).

국문 초록 (Abstract)

그래프 $G$의 변 색칠은 꼭짓점을 공유하는 두 변이 같은 값을 갖지 않도록 하는 $E(G)$에서 $\mathbb{Z}$로의 함수이다. 그래프 $G$의 모든 꼭짓점에 대해서, 그 꼭짓점과 인접한 변들에 부여된 값들이 연속이도록 하는 변 색칠이 존재한다면, 그래프 $G$가 변 구간 색칠 가능하다고 한다. 이 개념은 1987년 Asratian and Kamalian에 의하여 처음 소개되었으며, 많은 학자들이 이분그래프를 중심으로 이 문제에 대해서 연구해왔다.

이 학위논문에서는, 하이퍼그래프의 변 구간 색칠 문제를 소개하고 기본적인 성질들에 대해서 연구하였다. 또한 $(n+1,n+1,n)$-정규 삼분 3-유니폼 하이퍼그래프가 변 구간 $2n$-색칠이 가능하기 위한 필요충분 조건을 주었다. 추가적으로 Petrosyan and Khachatrian(2014)에 의하여 제시된 이분그래프들 중 변 구간 색칠 가능한 이분그래프를 더 찾았다.

목차 (Table of Contents)

• Contents
• Abstract i
• 1 Introduction 1
• 1.1 Basic definitions and notations for graphs and hypergraphs 1
• 1.2 Interval edge-coloring in graph 2
• 1.3 Topics of the thesis 6
• 1.3.1 Generalization to hypergraphs 6
• 1.3.2 Interval edge-colorability of small bipartite graphs . . 8
• 2 Interval edge-coloring in hypergraph 10
• 2.1 Definition and Examples 10
• 2.2 Interval edge-coloring on some regular hypergraph 11
• 2.2.1 2-regular hypergraphs 12
• 2.2.2 Tripartite 3-uniform hypergraphs 13
• 3 Some small interval edge-colorable bipartite graphs 20
• 3.1 ∆r,s,t 22
• 3.2 F(r1, . . . , rn2+n+1) 24
• 국문초록 38