Linearly Ordered Colourings of Hypergraphs
Linearly Ordered Colourings of Hypergraphs
复制标题
超图的线性有序着色
DOI：
10.1145/3570909
复制
发表时间：
2023
影响因子：
0.7
通讯作者：
Nakajima T
中科院分区：
文献类型：
--
作者：
Nakajima T
非均匀超图的线性有序k-着色赋{1，.，k}到每个顶点，使得在每个边中，颜色的（多）集合具有唯一的最大值。等价地，对于r = 3，如果一条边的两个顶点被赋予相同的颜色，那么第三个顶点被赋予更大的颜色（与经典的非单色着色中的不同颜色相反）。Barto，Battistelli和贝格[STACS'21]在Promise约束满足问题（PCSP）的背景下研究了3-均匀超图上的LO着色。我们证明了两个结果：第一，给定一个允许LO 2-着色的3-一致超图，我们可以在多项式时间内找到一个满足k=O（\sqrt [3]{n \log \log n / \log n} \）的LOk-着色;第二，给定一个允许LO 2-着色的r-一致超图，我们证明了对每个常数一致度r ≥k+2，找到一个LOk-着色的NP-困难性.事实上，我们确定了所有一致性r ≥ 3的多态仆从之间的关系，这揭示了r <k+2和r ≥k+2之间的关键区别，这可能是独立的兴趣。利用PCSP的代数方法，我们实际上给出了一个更一般的结果，证明了对于2 ≤kandr ≤kandr≥ k-kandr + 4，找到LO-着色一致超图的LOk-着色是NP-困难的。
A linearly ordered (LO)k-colouring of anr-uniform hypergraph assigns an integer from {1, ... ,k} to every vertex so that, in every edge, the (multi)set of colours has a unique maximum. Equivalently, forr= 3, if two vertices in an edge are assigned the same colour, then the third vertex is assigned a larger colour (as opposed to a different colour, as in classic non-monochromatic colouring). Barto, Battistelli, and Berg [STACS’21] studied LO colourings on 3-uniform hypergraphs in the context of promise constraint satisfaction problems (PCSPs). We show two results.First, given a 3-uniform hypergraph that admits an LO 2-colouring, one can find in polynomial time an LOk-colouring with \( k=O(\sqrt [3]{n \log \log n / \log n} \) .Second, given anr-uniform hypergraph that admits an LO 2-colouring, we establish NP-hardness of finding an LOk-colouring for every constant uniformityr≥k+2. In fact, we determine relationships between polymorphism minions for all uniformitiesr≥ 3, which reveals a key difference betweenr<k+2 andr≥k+2 and which may be of independent interest. Using the algebraic approach to PCSPs, we actually show a more general result establishing NP-hardness of finding an LOk-colouring for LO ℓ-colourabler-uniform hypergraphs for 2 ≤ ℓ ≤kandr≥k- ℓ + 4.
登录
查看更多内容
具有多对数颜色的着色 2 色超图的 NP 硬度
DOI：
10.4230/lipics.icalp.2018.15
发表时间：
2018
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Amey Bhangale
通讯作者：
Amey Bhangale
约束满足问题：复杂性和近似性（Dagstuhl 研讨会 18231）
DOI：
--
发表时间：
2018
期刊：
Dagstuhl Reports
影响因子：
--
作者：
Martin Grohe;V. Guruswami;Stanislav Živný
通讯作者：
Stanislav Živný
改进了彩虹着色的不近似性
DOI：
--
发表时间：
2018
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Per Austrin;Amey Bhangale;Aditya Potukuchi
通讯作者：
Aditya Potukuchi
关于超常数颜色数的4可色图着色的条件硬度
影响因子：
18.9
作者：
Irit Dinur;Igor Shinkar
通讯作者：
Igor Shinkar
做出独特选择的复杂性：近似 1-in-k SAT
影响因子：
18.9
作者：
V. Guruswami;L. Trevisan
通讯作者：
L. Trevisan