A note on the orientation covering number
A note on the orientation covering number
复制标题
关于方向覆盖号码的注释
DOI：
10.1016/j.dam.2021.08.006
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Janzer B
中科院分区：
文献类型：
--
作者：
Janzer B
给定一个图G，它的方向覆盖数σ（G）是最小的非负整数k，具有这样的性质：我们可以选择G的k个方向，使得只要x，y，z是G的顶点，且xy，xz ∈ E（G），则存在一个选择的方向，在该方向上xy和xz都远离x. Esperet，Gimbel和King证明了σ（G）≤ σ K χ（G），其中χ（G）是图G的色数，并提出了是否总是相等的问题.本文证明了σ（G）= σ（Kx（G））确实总是这种情况.我们还确定了精确的值σ（Kn）明确的“大多数”的值n。
Given a graph G, its orientation covering number σ (G) is the smallest non-negative integer k with the property that we can choose k orientations of G such that whenever x, y, z are vertices of G with x y, x z∈ E (G) then there is a chosen orientation in which both x y and x z are oriented away from x. Esperet, Gimbel and King showed that σ (G)≤ σ K χ (G), where χ (G) is the chromatic number of G, and asked whether we always have equality. In this note we prove that it is indeed always the case that σ (G)= σ (K χ (G)). We also determine the exact value of σ (K n) explicitly for ‘most’values of n.
登录
查看更多内容
DOI：
10.37236/2693
发表时间：
2013
期刊：
Electron. J. Comb.
影响因子：
--
作者：
A. Brouwer;C. F. Mills;W. Mills;A. Verbeek
通讯作者：
A. Verbeek
DOI：
10.1016/s0012-365x(98)00315-x
发表时间：
1999
期刊：
Discret. Math.
影响因子：
--
作者：
Serkan Hosten;W. Morris
通讯作者：
W. Morris
区间阶数和移位图
DOI：
10.1016/0095-8956(77)90048-x
发表时间：
2017
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Furedi;P. Hajnal;V. Rodl
通讯作者：
V. Rodl
DOI：
10.1016/j.dam.2010.08.012
发表时间：
2010
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Louis Esperet;J. Gimbel;Andrew D. King
通讯作者：
Andrew D. King