A study on partitioning planar graphs without 4-cycles and 5-cycles
- 주제(키워드) Planar graphs , Cycle length restriction , Steinberg’s conjecture , Improper coloring , Vertex partition.
- 주제(DDC) 510
- 발행기관 아주대학교
- 지도교수 박보람
- 발행년도 2022
- 학위수여년월 2022. 2
- 학위명 석사
- 학과 및 전공 일반대학원 수학과
- 실제URI http://www.dcollection.net/handler/ajou/000000031433
- 본문언어 한국어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
In 1976, Steinberg conjectured that planar graphs without 4-cycles and 5-cycles are 3-colorable. This conjecture attracted numerous researchers for about 40 years until it was disproved by Cohen-Addad et al. in 2017. How- ever, coloring planar graphs with restrictions on cycle lengths is still an active area of research, and the interest in this particular graph class remains. Recently, Cho, Choi, Park (2021) showed that for a planar graph G without 4-cycles and 5-cycles, V (G) is partitioned into two sets A and B such that G[A] and G[B] are forests with maximum degree three and four, respectively. In this thesis, we show that for a planar graph G without 4- cycles and 5-cycles, V (G) is partitioned into two sets A and B such that G[A] is a linear forest and G[B] has maximum degree at most 8.
more목차
1 Introduction 1
1.1 Definitions 1
1.2 History of Steinberg's Conjecture 2
1.3 The topic of this thesis and the main result 4
2 Preliminaries 5
2.1 Method for proofs 5
2.2 Definitions and basic lemmas in this thesis 5
3 Proof of Theorem 15 8
3.1 Reducible configurations 8
3.2 Discharging rules 14
국문초록 21
