지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2015.1
- 수록면
- 269 - 276 (8page)
이용수
초록· 키워드
오류제보하기
본 논문은 지금까지 미해결 문제로 알려진 정점 색칠 문제에 대한 Erd$\ddot{o}$s-Faber-Lov$\acute{a}$sz 추측을 증명하였다. Erd$\ddot{o}$s-Faber-Lov$\acute{a}$sz 추측은 "k개의 $K_k$-클릭 합 교차 그래프는 k개의 색으로 칠할 수 있다". 즉, x(G)=k이다". Erd$\ddot{o}$s-Faber-Lov$\acute{a}$sz 추측을 증명하기 위해 본 논문은 교차되는 정점수와 한 정점에서 교차되는 클릭수를 구하여 모두 짝수이면 그래프의 최소 차수 ${\delta}(G)$ 정점을 최대독립집합 (minimum Independent set, MIS)에 포함시키는 방법을 적용하고, 둘 중 어느 하나가 홀수이면 최대 차수 ${\Delta}(G)$ 정점을 MIS에 포함시키는 방법을 적용하였다. 알고리즘 수행결과 얻은 MIS 개수가 x(G)=k이다. $3{\leq}k{\leq}8$인 $K_k$-클릭 합 교차 그래프에 대해 실험한 결과 모든 그래프에서 x(G)=k를 얻는데 성공하였다. 결국, "k개의 $K_k$-클릭 합 교차 그래프는 k개의 색으로 칠할 수 있다".는 Erd$\ddot{o}$s-Faber-Lov$\acute{a}$sz 추측은 성립함을 증명하였다.
목차
등록된 정보가 없습니다.
참고문헌 (14)
참고문헌 신청
Wikipedia / Erdös-Faber-Lovász Conjecture
P. Erdös / 1992 / Advanced Problem 6664 / American Mathematical Monthly 100(7):692~693
L. Haddad / 2004 / A Clone-theoretic Formulation of the Erdös-Faber-Lovász Conjecture / Discussones Mathematicae Graph Theory 24(3):545~549
J. Kahn / 1992 / Coloring nearly-disjoint Hypergraphs with n+O(n)Colors / Journal of Combinatorial Theory, Series A 59(1):31~39
Graph Coloring
P. Erdös / 1992 / Advanced Problem 6664 / American Mathematical Monthly 100(7):692~693
L. Haddad / 2004 / A Clone-theoretic Formulation of the Erdös-Faber-Lovász Conjecture / Discussones Mathematicae Graph Theory 24(3):545~549
J. Kahn / 1992 / Coloring nearly-disjoint Hypergraphs with n+O(n)Colors / Journal of Combinatorial Theory, Series A 59(1):31~39
Graph Coloring
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
채색 그래프의 Max Clique 점 집합을 모두 구하는 알고리즘
한국정보통신학회 종합학술대회 논문집
2024 .10
-
최대 클릭 문제의 분할정복 알고리즘
한국정보기술학회논문지
2015 .06
-
경계 Lovasz-hinge 손실을 활용한 실시간 영상 분할 알고리즘의 미세 조정
한국방송미디어공학회 학술발표대회 논문집
2024 .06
-
싸이클 수 증가를 통한 Extended Least Difference Greedy Clique-cover 알고리즘의 개선
한국통신학회 학술대회논문집
2018 .06
-
그래프의 정점 연결성에 대한 최소 범위 할당
한국정보통신학회논문지
2017 .11
-
인덱스 부호 최적화를 위한 Extended Least Difference Greedy Clique-cover 알고리즘의 개선
한국통신학회 학술대회논문집
2018 .01
-
그래프 중심성들을 이용한 그래프 유사도 측정
한국컴퓨터정보학회논문지
2018 .12
-
중심성이 높은 정점의 변화에 따른 네트워크 특성 분석
한국컴퓨터정보학회논문지
2017 .03
-
Interval-Valued Fuzzy Graphs
INTERNATIONAL JOURNAL of FUZZY LOGIC and INTELLIGENT SYSTEMS
2020 .12
-
A Graph Embedding Technique for Weighted Graphs Based on LSTM Autoencoders
JIPS(Journal of Information Processing Systems)
2020 .01
-
The Classification of random graph models using graph centralities
한국컴퓨터정보학회논문지
2019 .07
-
그래프데이터베이스 기반 통신망 운영관리 방안
한국정보통신학회 종합학술대회 논문집
2022 .05
-
Unified Graph Clustering via Learning Robust and Structured Graph
대한전자공학회 학술대회
2019 .06
-
그래프 정보를 이용한 그래프 구조 간략화 알고리즘
제어로봇시스템학회 국내학술대회 논문집
2016 .03
-
최대 클릭 문제에 관한 최대차수 정점 기반 알고리즘
한국컴퓨터정보학회논문지
2015 .01
-
Graph Structure Analysis and Classification Framework using Graph Convolutional Network
대한산업공학회 춘계공동학술대회 논문집
2023 .05
-
Similarity Evalution between Graphs: A Formal Concept Analysis Approach
JIPS(Journal of Information Processing Systems)
2017 .01
-
Graph R-CNN을 이용한 Auto-Encoding Scene Graphs
한국정보과학회 학술발표논문집
2020 .12
-
관계형데이터를 이용한 그래프 데이터베이스의 모델별 구조 분석과 쿼리 성능 비교 연구
멀티미디어학회논문지
2019 .09
-
Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem
한국컴퓨터정보학회논문지
2015 .07
이 논문의 저자 정보
최근 본 자료
댓글(0)
0