Relaxations of Square Coloring
- 주제(키워드) square coloring , odd coloring , proper conflict-free coloring , strong odd coloring
- 주제(DDC) 510
- 발행기관 아주대학교 일반대학원
- 지도교수 Boram Park
- 발행년도 2024
- 학위수여년월 2024. 8
- 학위명 박사
- 학과 및 전공 일반대학원 수학과
- 실제URI http://www.dcollection.net/handler/ajou/000000033996
- 본문언어 영어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
A square coloring of a graph G is a proper coloring of G such that two vertices at distance at most 2 receive distinct colors. After Wegner’s paper in 1977, a square coloring has been an interesting object of many researchers and various relaxations have been introduced. Proper conflict-free coloring and odd coloring are relaxations of square coloring, which are introduced recently and attracted great interest between researchers. In this thesis, we introduce two new concepts of colorings related to proper conflict-free coloring and odd coloring, where they are not only variants of proper conflict-free coloring or odd coloring but also relaxations of square coloring. A proper h-conflict-free coloring of a graph G is a proper coloring of G such that for each vertex v, there are min{degG(v), h} colors appearing uniquely in its neighbor- hood. We obtain an upper bound for the proper h-conflict-free chromatic number of G in linear terms of ∆(G). In addition, we introduce a notion of strong odd coloring which is a proper coloring of G such that for each vertex each color in its neighborhood appears an odd number of times, and then explore observations related to it. keywords : square coloring, odd coloring, proper conflict-free coloring, strong odd coloring
more목차
1 Introduction 1
1.1 Preliminaries 1
1.1.1 Basic definitions in graph theory 1
1.1.2 Square coloring 3
1.2 Proper conflict-free coloring and odd coloring 6
1.2.1 Proper conflict-free coloring 8
1.2.2 Odd coloring 13
1.3 Main results of the thesis 16
1.3.1 Proper h-conflict-free coloring 17
1.3.2 Strong odd coloring 19
2 Brooks-type theorem of proper h-conflict-free coloring 23
2.1 Proof of Theorem A.1 25
2.1.1 The case when h = ∆− 2 25
2.1.2 The case when h ≤ ∆− 3 26
2.2 Proof of Theorem A.3 42
3 Strong odd coloring on sparse graphs 44
3.1 Preliminaries 45
3.2 Strong odd (∆ + 4)-coloring 50
3.3 Strong odd (∆ + 3)-coloring 57
3.3.1 Proof of Theorem B.2 57
3.3.2 Proof of Theorem B.3 62
References 69
