2021年9月
Proper Colorings of Plane Quadrangulations Without Rainbow Faces
GRAPHS AND COMBINATORICS
- ,
- ,
- 巻
- 37
- 号
- 5
- 開始ページ
- 1873
- 終了ページ
- 1890
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1007/s00373-021-02350-5
- 出版者・発行元
- SPRINGER JAPAN KK
We consider a proper coloring of a plane graph such that no face is rainbow, where a face is rainbow if any two vertices on its boundary have distinct colors. Such a coloring is said to be proper anti-rainbow. A plane quadrangulation G is a plane graph in which all faces are bounded by a cycle of length 4. In this paper, we show that the number of colors in a proper anti-rainbow coloring of a plane quadrangulation G does not exceed 3 alpha(G)/2, where alpha(G) is the independence number of G. Moreover, if the minimum degree of G is 3 or if G is 3-connected, then this bound can be improved to 5 alpha(G)/4 or 7 alpha(G)/6 + 1/3, respectively. All of these bounds are tight.
- リンク情報
- ID情報
-
- DOI : 10.1007/s00373-021-02350-5
- ISSN : 0911-0119
- eISSN : 1435-5914
- Web of Science ID : WOS:000660805200001