Asymptotic behavior of the chromatic index for hypergraphs

DOI10.1016/0097-3165(89)90074-5zbMATH Open0729.05038OpenAlexW2042703645MaRDI QIDQ805633FDOQ805633

Authors: Nicholas Pippenger, Joel Spencer 

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0097-3165(89)90074-5

Recommendations

• An asymptotic upper bound for the chromatic index of random hypergraphs
• Asymptotically good list-colorings
• scientific article; zbMATH DE number 736299
• Asymptotics of the chromatic index for multigraphs
• Chromatic index of simple hypergraphs

zbMATH Keywords

hypergraphsmaximum degreematchingspackingschromatic indexedge partitionSteiner triple-system

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Triple systems (05B07)

Cites Work

• On a packing and covering problem
• Title not available (Why is that?)
• Near perfect coverings in graphs and hypergraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two combinatorial covering theorems
• On the Size of a Maximum Transversal in a Steiner Triple System
• Asymptotically good coverings

Cited In (94)

• The \(n\)-queens completion problem
• Hanani triple systems
• Packing spanning graphs from separable families
• Harmonious and achromatic colorings of fragmentable hypergraphs
• Covering the edges of a random graph by cliques
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Near-optimal, distributed edge colouring via the nibble method
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Packing minor-closed families of graphs into complete graphs
• Note on asymptotically good packings
• Long gaps between primes
• Minimum \(H\)-decompositions of graphs: edge-critical case
• The Erdős matching conjecture and concentration inequalities
• Lower bounds on circuit depth of the quantum approximate optimization algorithm
• Near-optimal distributed edge coloring
• Edge-coloring of 3-uniform hypergraphs
• On the chromatic index of random uniform hypergraphs
• The chromatic index of projective triple systems
• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
• Triangle packings and 1-factors in oriented graphs
• The genus of a random graph
• Multicolor Ramsey numbers for triple systems
• Nearly-perfect hypergraph packing is in NC
• Integer and fractional packings of hypergraphs
• On a conjecture of Erdős on locally sparse Steiner triple systems
• Near-optimal list colorings
• Fractional v. integral covers in hypergraphs of bounded edge size
• Nearly perfect matchings in regular simple hypergraphs
• The genus of a random bipartite graph
• Randomly colouring graphs (a combinatorial view)
• New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
• A better bound on the size of rainbow matchings
• The existence of \(k\)-radius sequences
• Every \(H\)-decomposition of \(K_n\) has a nearly resolvable alternative
• Novák's conjecture on cyclic Steiner triple systems and its generalization
• Asymptotic packing via a branching process
• Decomposition of bi-colored square arrays into balanced diagonals
• Rainbow matchings for 3-uniform hypergraphs
• On a hypergraph matching problem
• Every Steiner triple system contains almost spanning \(d\)-ary hypertree
• Decomposing hypergraphs into cycle factors
• Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors
• Probabilistic methods in coloring and decomposition problems
• The chromatic number of finite group Cayley tables
• On the degree, size, and chromatic index of a uniform hypergraph
• Minimum \(H\)-decompositions of graphs
• Covers and partial transversals of Latin squares
• Resolution of the Oberwolfach problem
• Chromatic index of simple hypergraphs
• A proof of the Erdős-Faber-Lovász conjecture
• On a problem of Erdős and Moser
• On generalized Ramsey theory: The bipartite case
• Almost all Steiner triple systems are almost resolvable
• Asymptotics of the chromatic number for quasi-line graphs
• On the genus of a random graph
• Concentration of non‐Lipschitz functions and applications
• Asymptotically good list-colorings
• A natural barrier in random greedy hypergraph matching
• A Ramsey‐type problem and the Turán numbers*
• Steiner triple systems without parallel classes
• Invitation to intersection problems for finite sets
• Large gaps between consecutive prime numbers containing perfect \(k\)-th powers of prime numbers
• Strong edge colorings of uniform graphs
• Chromatic index of hypergraphs and Shannon's theorem
• Decompositions into isomorphic rainbow spanning trees
• On Brooks' Theorem for Sparse Graphs
• A note on a conjecture by Füredi
• Steiner triple systems with high chromatic index
• Circulants and the chromatic index of Steiner triple systems
• New bounds on the size of nearly perfect matchings in almost regular hypergraphs
• Hamilton transversals in random Latin squares
• A lower bound on the multicolor size-Ramsey numbers of paths in hypergraphs
• On the \((6,4)\)-problem of Brown, Erdős, and Sós
• Rainbow structures in locally bounded colorings of graphs
• Induced decompositions of highly dense graphs
• Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
• Minimum rainbow \(H\)-decompositions of graphs
• Minimum rainbow \(H\)-decompositions of graphs
• Decomposition of bicolored square arrays into bichromatic diagonals
• Rainbow spanning structures in graph and hypergraph systems
• A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems
• On asymptotic packing of convex geometric and ordered graphs
• Rainbow perfect matchings for 4-uniform hypergraphs
• Boolean tensor decomposition for conjunctive queries with negation
• A special case of Vu's conjecture: colouring nearly disjoint graphs of bounded maximum degree
• Approximate generalized Steiner systems and near-optimal constant weight codes
• Resolution of the Oberwolfach problem
• Prominent examples of flip processes
• Graph and hypergraph colouring via nibble methods: a survey
• Almost all optimally coloured complete graphs contain a rainbow Hamilton path
• Triple systems with no three triples spanning at most five points
• Packing paths in Steiner triple systems
• An asymptotic upper bound for the chromatic index of random hypergraphs
• Large monochromatic components in colorings of complete hypergraphs

This page was built for publication: Asymptotic behavior of the chromatic index for hypergraphs

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