2021年5月
Single-conflict colouring
JOURNAL OF GRAPH THEORY
- ,
- ,
- ,
- 巻
- 97
- 号
- 1
- 開始ページ
- 148
- 終了ページ
- 160
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1002/jgt.22646
- 出版者・発行元
- WILEY
Given a multigraph, suppose that each vertex is given a local assignment of k colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no edge has both of its local colours chosen. The least k for which this is always possible given any set of local assignments we call the single-conflict chromatic number of the graph. This parameter is closely related to separation choosability and adaptable choosability. We show that single-conflict chromatic number of simple graphs embeddable on a surface of Euler genus g is O(g(1/4) log g) as g -> infinity. This is sharp up to the logarithmic factor.
- リンク情報
-
- DOI
- https://doi.org/10.1002/jgt.22646
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000585085100001&DestApp=WOS_CPL
- URL
- http://www.scopus.com/inward/record.url?eid=2-s2.0-85096659441&partnerID=MN8TOARS
- ID情報
-
- DOI : 10.1002/jgt.22646
- ISSN : 0364-9024
- eISSN : 1097-0118
- ORCIDのPut Code : 112489912
- SCOPUS ID : 85096659441
- Web of Science ID : WOS:000585085100001