A note on panchromatic colorings

DOI10.1016/J.DISC.2017.10.030zbMATH Open1378.05052arXiv1705.03797OpenAlexW2962842655MaRDI QIDQ1690224FDOQ1690224

Authors: Danila Cherkashin 

Publication date: 19 January 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: This paper studies the quantity $p(n,r)$, that is the minimal number of edges of an $n$-uniform hypergraph without panchromatic coloring (it means that every edge meets every color) in $r$ colors. If $rleqcfracnlnn$ then all bounds have a type $A_1(n,lnn,r)(fracrr-1{)}^{n}leqp(n,r)leq{A}_2(n,r,lnr)(fracrr-1{)}^n$, where $A_1$, $A_2$ are some algebraic fractions. The main result is a new lower bound on $p(n,r)$ when $r$ is at least $csqrtn$; we improve an upper bound on $p(n,r)$ if $n=o(r^{3/2})$. Also we show that $p(n,r)$ has upper and lower bounds depend only on $n/r$ when the ratio $n/r$ is small, which can not be reached by the previous probabilistic machinery. Finally we construct an explicit example of a hypergraph without panchromatic coloring and with $(fracrr-1+o(1){)}^n$ edges for $r=o(sqrtfracnlnn)$.

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

Recommendations

• The existence of panchromatic colourings for uniform hypergraphs
• Chain method for panchromatic colorings of hypergraphs
• Extremal problems for panchromatic colourings of uniform hypergraphs
• Panchromatic colorings of random hypergraphs
• Random constructions of hypergraphs with large girth and without panchromatic colorings

zbMATH Keywords

hypergraph coloringspanchromatic colorings

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cites Work

• Title not available (Why is that?)
• The probabilistic method
• Title not available (Why is that?)
• The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
• Color-critical graphs and hypergraphs with few edges: a survey
• On a combinatorial problem. II
• Choice Numbers of Graphs: a Probabilistic Approach
• On the construction of 3-chromatic hypergraphs with few edges
• Greedy colorings of uniform hypergraphs
• Improvement of the lower bound in the Kostochka problem of panchromatic coloring of a hypergraph
• On a theorem of Erdős, Rubin, and Taylor on choosability of complete bipartite graphs
• Density conditions for panchromatic colourings of hypergraphs
• On a generalization of Rubin's theorem
• The existence of panchromatic colourings for uniform hypergraphs

Cited In (14)

• Coloring hypergraphs with bounded cardinalities of edge intersections
• Density conditions for panchromatic colourings of hypergraphs
• Panchromatic colorings of random hypergraphs
• The existence of panchromatic colourings for uniform hypergraphs
• Extremal problems for panchromatic colourings of uniform hypergraphs
• Panchromatic 3-colorings of random hypergraphs
• Extremal problems in hypergraph colourings
• Title not available (Why is that?)
• Two values of the chromatic number of a sparse random graph
• Chain method for panchromatic colorings of hypergraphs
• Random constructions of hypergraphs with large girth and without panchromatic colorings
• Equitable colorings of hypergraphs with few edges
• The list-chromatic number of complete multipartite hypergraphs and multiple covers by independent sets
• Equitable colorings of hypergraphs with \(r\) colors

This page was built for publication: A note on panchromatic colorings

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