Suppr超能文献

单冲突着色

Single-conflict colouring.

作者信息

Dvořák Zdeněk, Esperet Louis, Kang Ross J, Ozeki Kenta

机构信息

Computer Science Institute (CSI) Charles University Prague Czech Republic.

CNRS, G-SCOP Université Grenoble Alpes Grenoble France.

出版信息

J Graph Theory. 2021 May;97(1):148-160. doi: 10.1002/jgt.22646. Epub 2020 Nov 4.

Abstract

Given a multigraph, suppose that each vertex is given a local assignment of 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 for which this is always possible given any set of local assignments we call the 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 is as . This is sharp up to the logarithmic factor.

摘要

给定一个多重图,假设给每个顶点的关联边赋予一组局部颜色。我们感兴趣的是,是否存在一种为每个顶点选择一种局部颜色的方式,使得没有边的两种局部颜色都被选中。对于给定的任何一组局部赋值,总能做到这一点的最小数,我们称之为图的[相关参数名称未给出,暂无法准确翻译]。这个参数与分离可选择性和适应性可选择性密切相关。我们证明,可嵌入到欧拉亏格为[具体亏格未给出,暂无法准确翻译]的曲面的简单图的单冲突色数为[具体表达式未给出,暂无法准确翻译],其中[相关条件未给出,暂无法准确翻译]。这在对数因子范围内是精确的。

相似文献

1
Single-conflict colouring.单冲突着色
J Graph Theory. 2021 May;97(1):148-160. doi: 10.1002/jgt.22646. Epub 2020 Nov 4.
2
The complexity of frugal colouring.节俭着色的复杂性。
Arab J Math. 2021;10(1):51-57. doi: 10.1007/s40065-021-00311-7. Epub 2021 Jan 29.
3
Local total anti-magic chromatic number of graphs.图的局部全反魔法色数
Heliyon. 2023 Jul 4;9(7):e17761. doi: 10.1016/j.heliyon.2023.e17761. eCollection 2023 Jul.
4
Occupancy fraction, fractional colouring, and triangle fraction.占有率、分数着色和三角形分数。
J Graph Theory. 2021 Jul;97(4):557-568. doi: 10.1002/jgt.22671. Epub 2021 Mar 9.
6
The Complexity of Two Colouring Games.双色游戏的复杂性
Algorithmica. 2023;85(4):1067-1090. doi: 10.1007/s00453-022-01069-w. Epub 2022 Nov 24.
7
Dataset of Edmonds' bi-vectors and tri-vectors with realizations.包含实现的埃德蒙兹双向量和三向量数据集。
Data Brief. 2024 Jul 31;56:110785. doi: 10.1016/j.dib.2024.110785. eCollection 2024 Oct.
8
Application of graph colouring to biological networks.图着色在生物网络中的应用。
IET Syst Biol. 2010 May;4(3):185-92. doi: 10.1049/iet-syb.2009.0038.
9
On the antimagicness of generalized edge corona graphs.关于广义边冠图的反魔法性
Heliyon. 2024 Jan 5;10(2):e24002. doi: 10.1016/j.heliyon.2024.e24002. eCollection 2024 Jan 30.
10
The reflexive edge strength on some almost regular graphs.某些几乎正则图上的自反边强度。
Heliyon. 2021 May 6;7(5):e06991. doi: 10.1016/j.heliyon.2021.e06991. eCollection 2021 May.

文献检索

告别复杂PubMed语法,用中文像聊天一样搜索,搜遍4000万医学文献。AI智能推荐,让科研检索更轻松。

立即免费搜索

文件翻译

保留排版,准确专业,支持PDF/Word/PPT等文件格式,支持 12+语言互译。

免费翻译文档

深度研究

AI帮你快速写综述,25分钟生成高质量综述,智能提取关键信息,辅助科研写作。

立即免费体验