The existence of uniform hypergraphs for which the interpolation property of complete coloring fails

DOI10.1016/J.DISC.2021.112722MaRDI QIDQ2065902zbMATH OpenOpenAlexFDO

Authors Nastaran Haghparast, Morteza Hasanvand, Yumiko Ohno

Publication date 13 January 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.02034

zbMATH Keywords

complete coloringface hypergraphhypergraphtriangulation

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: In 1967 Harary, Hedetniemi, and Prins showed that every graph $G$ admits a complete $t$-coloring for every $t$ with $chi(G)letlepsi(G)$, where $chi(G)$ denotes the chromatic number of $G$ and $psi(G)$ denotes the achromatic number of $G$ which is the maximum number $r$ for which $G$ admits a complete $r$-coloring. Recently, Edwards and Rzc a.{z}ewski (2020) showed that this result fails for hypergraphs by proving that for every integer $k$ with $kge9$, there exists a $k$-uniform hypergraph $H$ with a complete $chi(H)$-coloring and a complete $psi(H)$-coloring, but no complete $t$-coloring for some $t$ with $chi(H)<t<psi(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 $kge3$ and settle their problems by giving several kinds of $3$-uniform hypergraphs. In particular, we disprove a recent conjecture due to Matsumoto and the third author (2020) who suggested a special family of $3$-uniform hypergraph to satisfy the desired interpolation property.

Review text

The authors study the so-called interpolation property for uniform hypergraphs, which concerns complete (vertex) colorings of uniform hypergraphs. The main result of the paper states that for any \(k \geq 3\), there exist \(k\)-uniform hypergraphs that do not have the interpolation property in a strong sense (defined below). A \(k\)-uniform hypergraph \(H\) is a hypergraph whose edges all have cardinality \(k\). A \(t\)-coloring of a hypergraph \(H\) is an assignment of colors to the vertices of \(H\), where the colors come from a collection of \(t\) colors. A coloring is proper if any two vertices that are in an edge receive distinct colors. The chromatic number of \(H\), denoted by \(\chi(H)\), is the minimum number of colors needed to properly color \(H\). A coloring of a \(k\)-uniform hypergraph \(H\) is complete if is proper and every subset of \(k\)-colors appears on at least one edge of \(H\). The achromatic number of \(H\), denoted by \(\psi(H)\) is the largest integer \(t\) such that there is a complete \(t\)-coloring of \(H\). It is known that every graph \(G\) has a complete coloring. A result of \textit{F. Harary} et al. [Port. Math. 26, 453--462 (1967; Zbl 0187.20903)] states that that if \(G\) is a graph, then \(G\) admits a \(t\)-coloring for every \(t\) such that \(\chi(G) \leq t \leq \psi(G)\). In other words, every graph has the interpolation property. On the other hand, \textit{K. Edwards} and \textit{P. Rzążewski} [Discrete Math. 343, No. 2, Article ID 111673, 12 p. (2020; Zbl 1429.05065)] showed that, for all \(k \geq 9\), there exist hypergraphs \(H\) which have complete \(\chi(H)\)-coloring and \(\psi(H)\)-colorings, but no complete \(t\)-coloring for some \(\chi(H) \leq t \leq \psi(H)\). The authors strengthen the result of Edwards and Rzążewski [loc. cit.], and show that for any \(k \geq 3\), there exist hypergraphs \(H\) which have complete \(\chi(H)\)-coloring and \(\psi(H)\)-colorings, but no complete \(t\)-coloring for any \(\chi(H) \leq t \leq \psi(H)\).

Recommendations

• The existence of panchromatic colourings for uniform hypergraphs
• scientific article; zbMATH DE number 1305101
• Extremal problems for colourings of uniform hypergraphs
• scientific article; zbMATH DE number 568840
• A contribution to the chromatic theory of uniform hypergraphs
• Interpolation theorem for partial Grundy coloring
• On the construction of non-2-colorable uniform hypergraphs
• Defective colorings on k-uniform hypergraphs
• On colorings of non-uniform hypergraphs without short cycles
• Coloring d-embeddable k-uniform hypergraphs

Cites work

• A new proof of 3-colorability of Eulerian triangulations
• Coloring face-hypergraphs of graphs on surfaces
• Complete colourings of hypergraphs
• Every planar map is four colorable
• Facial achromatic number of triangulations on the sphere
• Fast generation of planar graphs
• Harmonious and achromatic colorings of fragmentable hypergraphs
• scientific article; zbMATH DE number 3298599 (Why is no real title available?)

Cited in

(3)

• Complete colourings of hypergraphs
• Defective colorings on k-uniform hypergraphs
• Forbidden subgraphs and complete partitions

Describes a project that uses

Uses Software

• plantri

This page was built for publication: The existence of uniform hypergraphs for which the interpolation property of complete coloring fails

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2065902)