A short proof of the existence of highly chromatic hypergraphs without short cycles

DOI10.1016/0095-8956(79)90084-4zbMath0413.05039OpenAlexW2010887931MaRDI QIDQ1260043

Jaroslav Nešetřil, Vojtěch Rödl

Publication date: 1979

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

Full work available at URL: https://doi.org/10.1016/0095-8956(79)90084-4

zbMATH Keywords

uniform hypergraphchromatic numberamalgamationhighly chromatic hypergraphs without short cycles

Mathematics Subject Classification ID

Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Graph theory (05C99)

Related Items (41)

Graphs and digraphs with given girth and connectivity ⋮ Distance Preserving Ramsey Graphs ⋮ Compactness and finite equivalence of infinite digraphs ⋮ A class of edge critical 4-chromatic graphs ⋮ A non-covering graph of girth six ⋮ Some theorems concerning the star chromatic number of a graph ⋮ The partite construction and Ramsey set systems ⋮ High girth and extendability ⋮ Dualities and dual pairs in Heyting algebras ⋮ Partitions of graphs into cographs ⋮ The number of dependent arcs in an acyclic orientation ⋮ Directed acyclic graphs with the unique dipath property ⋮ Independent Transversals in Sparse Partite Hypergraphs ⋮ The fractional chromatic number of Zykov products of graphs ⋮ Attempting perfect hypergraphs ⋮ Generalised dualities and maximal finite antichains in the homomorphism order of relational structures ⋮ Coloring Hasse diagrams and disjointness graphs of curves ⋮ Constraints, MMSNP and expander relational structures ⋮ Coloring graphs without short cycles and long induced paths ⋮ A hypergraph-free construction of highly chromatic graphs without short cycles ⋮ Degrees in oriented hypergraphs and sparse Ramsey theory ⋮ Simple proof of the existence of restricted Ramsey graphs by means of a partite construction ⋮ Randomly colouring graphs (a combinatorial view) ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Chromatic number of Hasse diagrams, eyebrows and dimension ⋮ Graph properties and hypergraph colourings ⋮ Box and Segment Intersection Graphs with Large Girth and Chromatic Number ⋮ A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth ⋮ Mycielski type constructions for hypergraphs associated with fractional colorings ⋮ Chromatic capacity and graph operations ⋮ On a construction of graphs with high chromatic capacity and large girth ⋮ Minors of Boolean functions with respect to clique functions and hypergraph homomorphisms ⋮ Independent coverings and orthogonal colourings ⋮ Incidence posets and cover graphs ⋮ On sets of integers with the Schur property ⋮ Unnamed Item ⋮ All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms) ⋮ Hasse diagrams with large chromatic number ⋮ Sparse Ramsey graphs ⋮ Combinatorial partitions of finite posets and lattices - Ramsey lattices ⋮ On graphs that can be oriented as diagrams of ordered sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partitions of finite relational and set systems
• Graph Theory and Probability
• On chromatic number of graphs and set-systems
• On chromatic number of finite set-systems

This page was built for publication: A short proof of the existence of highly chromatic hypergraphs without short cycles