Sparse colour-critical hypergraphs

DOI10.1007/BF02125892MaRDI QIDQ809089zbMATH OpenOpenAlexWikidataFDO

Authors N. E. Zubov

Publication date 1989

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02125892

zbMATH Keywords

chromatic numberhypergraphlinear

Mathematics Subject Classification ID

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

Review text

A hypergraph H is called an n-hypergraph if the order of each of its edges equals n. It is called s-critical with respect to colouring if its chromatic number is r and the removal of any edge results in a graph which has chromatic number r-1. A hypergraph is called linear if the intersection of two arbitrary edges is at most 1 vertex. The main question treated in this paper is how few edges on (m,n,r)-graph or linear (m,n,r)-graph may possess. Estimates for the least numbers of that kind are given.

Recommendations

• Color-critical graphs and hypergraphs with few edges: a survey
• scientific article; zbMATH DE number 5546
• On the chromaticity of quasi linear hypergraphs
• Color critical hypergraphs with many edges
• On the number of edges in colour-critical graphs and hypergraphs

Cites work

• A Note on a Combinatorial Problem of ErdŐS and Hajnal
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• Coloring n-sets red and blue
• Colour-critical graphs and hypergraphs
• Ein kombinatorisches Problem von P. Erdős und A. Hajnal
• scientific article; zbMATH DE number 3188524 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• On 3-chromatic hypergraphs
• On A Combinatorial Problem III
• On A Combinatorial Problem of Erdös
• On a Combinatorial Problem of Erdös and Hajnal
• On a combinatorial problem. II
• On chromatic number of graphs and set-systems
• On Property B of Families of Sets
• On property B and on Steiner systems
• ON THE TWO-COLOURING OF HYPERGRAPHS
• The enumeration problem for color critical linear hypergraphs
• The existence problem for colour critical linear hypergraphs

Cited in

(8)

• Square critically 3-chromatic hypergraphs
• Color-critical graphs and hypergraphs with few edges and no short cycles
• Sparse \(H\)-colourable graphs of bounded maximum degree
• On the number of edges in hypergraphs critical with respect to strong colourings
• Restricted extension of sparse partial edge colorings of hypercubes
• The local cut lemma
• On the chromaticity of quasi linear hypergraphs
• Color-critical graphs and hypergraphs with few edges: a survey

This page was built for publication: Sparse colour-critical hypergraphs

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