서지주요정보
Chromatic number, Clique number and $n$-join of Graphs = 그래프의 Chromatic number, Clique number, $n$-join
서명 / 저자 Chromatic number, Clique number and $n$-join of Graphs = 그래프의 Chromatic number, Clique number, $n$-join / Rin-Gi Kim.
발행사항 [대전 : 한국과학기술원, 2011].

소장정보

등록번호

8023116

소장위치/청구기호

학술문화관(문화관) 보존서고

MMA 11018

휴대폰 전송

도서상태

이용가능(대출불가)

사유안내

반납예정일

리뷰정보

초록정보

The {\em chromatic number} of a graph $G$, denoted by $\chi(G)$, is the smallest number of colors needed to color every vertex of $G$ so that no two adjacent vertices have the same color. A {\em clique} in a graph is a set of pairwise adjacent vertices. The {\em clique number of a graph $G$}, denoted by $\omega(G)$, is the number of vertices in a maximum clique in $G$. A graph class $\mathcal{G}$ is said to be {\em $\chi$-bounded} if there is a function $f:\mathbb{N}\cup \{0\} \to \mathbb{R}$ such that $\chi(H) \le f(\omega(H))$ for every induced subgraph $H$ of $G$. We show that if a graph class $\mathcal{G}$ is $\chi$-bounded, then so is the class of restricted $n$-join graphs of $\mathcal{G}$.

그래프 $G$의 chromatic number란, $G$의 각 꼭짓점을 색칠하는데, 인접한 두 점은 같은 색을 갖지 않도록 하기 위해 필요한 최소한의 색의 수이며, $\chi(G)$로 표기한다. 그래프 $G$의 clique이란 서로가 모두 연결되어 있는 $G$의 꼭짓점으로 구성된 집합이다. 그리고 그래프 $G$의 clique number 란 $G$의 clique 중 가장 많은 꼭짓점을 포함하고 있는 것의 크기이며, $\omega(G)$로 표기한다. 그래프의 집합 $\mathcal{G}$가 다음 조건을 만족하면, $\mathcal{G}$를 $\chi$-bounded라고 한다 : 임의의 $G\in \mathcal{G}$와 $G$의 모든 induced subgraph $H$에 대하여, $\chi(H)\le f(\omega(H))$를 만족하는 $f:\mathbb{N} \cup\{0\} \to \mathbb{R}$가 존재한다. 이 논문에서는 $\chi$-bounded인 그래프 집합 $\mathcal{G}$가 주어져 있을 때, $\mathcal{G}$의 `제한된 $n$-join 그래프 집합 $\overline{\mathcal{G}}^n$`도 $\chi$-bounded라는 것을 증명하였다.

서지기타정보

서지기타정보
청구기호 {MMA 11018
형태사항 ii, 12 p. : 삽화 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 김린기
지도교수의 영문표기 : Sang-il Oum
지도교수의 한글표기 : 엄상일
학위논문 학위논문(석사) - 한국과학기술원 : 수리과학과,
서지주기 References : p.9
QR CODE

책소개

전체보기

목차

전체보기

이 주제의 인기대출도서