그래프 $G$의 변 색칠은 꼭짓점을 공유하는 두 변이 같은 값을 갖지 않도록 하는 $E(G)$에서 $\mathbb{Z}$로의 함수이다. 그래프 $G$의 모든 꼭짓점에 대해서, 그 꼭짓점과 인접한 변들에 부여된 값들이 연속이도록 하는 변 색칠이 존재한다면, 그래프 $G$가 변 구간 색칠 가능하다고 한다. 이 개념은 1987년 Asratian and Kamalian에 의하여 처음 소개되었으며, 많은 학자들이 이분그래프를 중심으로 이 문제에 대해서 연구해왔다.
이 학위논문에서는, 하이퍼그래프의 변 구간 색칠 문제를 소개하고 기본적인 성질들에 대해서 연구하였다. 또한 $(n+1,n+1,n)$-정규 삼분 3-유니폼 하이퍼그래프가 변 구간 $2n$-색칠이 가능하기 위한 필요충분 조건을 주었다. 추가적으로 Petrosyan and Khachatrian(2014)에 의하여 제시된 이분그래프들 중 변 구간 색칠 가능한 이분그래프를 더 찾았다.
Alternative 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).
