論文

査読有り
2021年9月

Proper Colorings of Plane Quadrangulations Without Rainbow Faces

GRAPHS AND COMBINATORICS
  • Kengo Enami
  • ,
  • Kenta Ozeki
  • ,
  • Tomoki Yamaguchi

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.

リンク情報
DOI
https://doi.org/10.1007/s00373-021-02350-5
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000660805200001&DestApp=WOS_CPL
ID情報
  • DOI : 10.1007/s00373-021-02350-5
  • ISSN : 0911-0119
  • eISSN : 1435-5914
  • Web of Science ID : WOS:000660805200001

エクスポート
BibTeX RIS