On interval edge-coloring problem in hypergraphs
On interval edge-coloring problem in hypergraphs
- 주제(키워드) hypergraph , interval edge-coloring
- 발행기관 아주대학교 일반대학원
- 지도교수 박보람
- 발행년도 2018
- 학위수여년월 2018. 8
- 학위명 석사
- 학과 및 전공 일반대학원 수학과
- 실제URI http://www.dcollection.net/handler/ajou/000000027890
- 본문언어 영어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
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).
more초록/요약
그래프 $G$의 변 색칠은 꼭짓점을 공유하는 두 변이 같은 값을 갖지 않도록 하는 $E(G)$에서 $\mathbb{Z}$로의 함수이다. 그래프 $G$의 모든 꼭짓점에 대해서, 그 꼭짓점과 인접한 변들에 부여된 값들이 연속이도록 하는 변 색칠이 존재한다면, 그래프 $G$가 변 구간 색칠 가능하다고 한다. 이 개념은 1987년 Asratian and Kamalian에 의하여 처음 소개되었으며, 많은 학자들이 이분그래프를 중심으로 이 문제에 대해서 연구해왔다. 이 학위논문에서는, 하이퍼그래프의 변 구간 색칠 문제를 소개하고 기본적인 성질들에 대해서 연구하였다. 또한 $(n+1,n+1,n)$-정규 삼분 3-유니폼 하이퍼그래프가 변 구간 $2n$-색칠이 가능하기 위한 필요충분 조건을 주었다. 추가적으로 Petrosyan and Khachatrian(2014)에 의하여 제시된 이분그래프들 중 변 구간 색칠 가능한 이분그래프를 더 찾았다.
more목차
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
