論文

2021年5月

Single-conflict colouring

JOURNAL OF GRAPH THEORY
  • Zdenek Dvorak
  • ,
  • Louis Esperet
  • ,
  • Ross J. Kang
  • ,
  • Kenta Ozeki

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

エクスポート
BibTeX RIS