The existence of uniform hypergraphs for which the interpolation property of complete coloring fails
The existence of uniform hypergraphs for which the interpolation property of complete coloring fails
复制标题
完全着色插值性质失效的均匀超图的存在性
DOI：
10.1016/j.disc.2021.112722
复制
发表时间：
2022
影响因子：
0.8
通讯作者：
Ohno Yumiko
中科院分区：
文献类型：
--
作者：
Haghparast Nastaran;Hasanvand Morteza;Ohno Yumiko
1967年Harary，Hedetniemi，and Prins证明了图G对任意t都有完全t-染色，且χ（G）≤ t≤ λ（G），其中χ（G）表示图G的色数，λ（G）表示图G的消色数，它是图G有完全r-染色的最大数r.最近，Edwards和Rza Riza Eschenewski（2020）证明了对于任意整数k（k≥ 9），存在一个k-一致超图H，它具有完全χ（H）-染色和完全t（H）-染色，但对于某些t（x（H）< t<t（H）），它不具有完全t-染色。他们还问是否会存在这样一个3-一致超图的例子，并提出了另一个问题来加强他们的结果。本文将他们的结果推广到所有k≥ 3的情况，并通过给出几个3-一致超图的例子解决了他们的问题。特别地，我们反驳了最近由松本和Ohno（2020）提出的一个猜想，他们提出了一个特殊的3-一致超图族来满足所需的插值性质。
Abstract In 1967 Harary, Hedetniemi, and Prins showed that every graph G admits a complete t-coloring for every t with χ (G)≤ t≤ ψ (G), where χ (G) denotes the chromatic number of G and ψ (G) denotes the achromatic number of G which is the maximum number r for which G admits a complete r-coloring. Recently, Edwards and Rza̧żewski (2020) showed that this result fails for hypergraphs by proving that for every integer k with k≥ 9, there exists a k-uniform hypergraph H with a complete χ (H)-coloring and a complete ψ (H)-coloring, but no complete t-coloring for some t with χ (H)< t< ψ (H). They also asked whether there would exist such an example for 3-uniform hypergraphs and posed another problem to strengthen their result. In this paper, we generalize their result to all cases k with k≥ 3 and settle their problems by giving several examples of 3-uniform hypergraphs. In particular, we disprove a recent conjecture due to Matsumoto and Ohno (2020) who suggested a special family of 3-uniform hypergraph to satisfy the desired interpolation property.
登录
查看更多内容
DOI：
10.1016/j.endm.2015.06.042
发表时间：
2015
期刊：
Eur. J. Comb.
影响因子：
--
作者：
Michał Deͅbski;Zbigniew Lonc;Paweł Rzaͅżewski
通讯作者：
Paweł Rzaͅżewski
影响因子：
0.8
作者：
F. Harary;S. Hedetniemi;G. Prins
通讯作者：
G. Prins
DOI：
--
发表时间：
2006
期刊：
--
影响因子：
--
作者：
Iroon Polytechniou-
通讯作者：
Iroon Polytechniou-
DOI：
10.1016/j.disc.2019.111673
发表时间：
2020
期刊：
Discret. Math.
影响因子：
--
作者：
Keith J. Edwards;Paweł Rzaͅżewski
通讯作者：
Paweł Rzaͅżewski