On the degree, size, and chromatic index of a uniform hypergraph

DOI10.1006/JCTA.1996.2728MaRDI QIDQ5961544zbMATH OpenOpenAlexFDO

Authors Noga Alon, Jeong Han Kim

Publication date 18 August 1997

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/6785d179401e0ae123c92c0b4f8a2167b95b2817

zbMATH Keywords

chromatic indexdegreehypergraphsize

Mathematics Subject Classification ID

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

Review text

It is proved that an intersecting \(k\)-uniform hypergraph \(H\) in which no two edges share more than \(t\) common vertices and having maximum vertex degree \(D\) has at most \((t-1+{1\over t})D\) edges, provided that \(D\) is sufficiently large in terms of \(k\). This is a special case of a more general conjecture formulated in the paper.

Recommendations

• On the chromatic index of random uniform hypergraphs
• A contribution to the chromatic theory of uniform hypergraphs
• On the degree sequences of uniform hypergraphs
• The chromatic index of simple hypergraphs
• On chromaticity of hypergraphs
• On the sizes of vertex-k-maximal r-uniform hypergraphs
• On the chromatic index of almost all graphs
• Colourings of uniform hypergraphs with large girth and applications
• Asymptotic behavior of the chromatic index for hypergraphs
• scientific article; zbMATH DE number 4122017

Cited in

(19)

• Ramsey-nice families of graphs
• A tale of stars and cliques
• A note on G-intersecting families
• On the number of edges of a uniform hypergraph with a range of allowed intersections
• On the sizes of vertex-k-maximal r-uniform hypergraphs
• On the number of edges in a uniform hypergraph with a range of permitted intersections
• Lower bounds on circuit depth of the quantum approximate optimization algorithm
• Decomposition of bicolored square arrays into bichromatic diagonals
• Decomposition of bi-colored square arrays into balanced diagonals
• Coloring 2-intersecting hypergraphs
• Intersections of hypergraphs
• A stability theorem for matchings in tripartite 3-graphs
• Boolean tensor decomposition for conjunctive queries with negation
• On the chromatic index of random uniform hypergraphs
• Hypergraphs without non-trivial intersecting subgraphs
• The intersection spectrum of 3‐chromatic intersecting hypergraphs
• Graph and hypergraph colouring via nibble methods: a survey
• On t-Intersecting Hypergraphs with Minimum Positive Codegrees
• Uniform hypergraphs under certain intersection constraints between hyperedges

This page was built for publication: On the degree, size, and chromatic index of a uniform hypergraph

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