A note on generalized chromatic number and generalized girth

DOI10.1016/S0012-365X(99)00165-XMaRDI QIDQ1970697zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Douglas B. West

Publication date 21 March 2000

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numbergirthforbidden subgraph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: ErdH{o}s proved that there are graphs with arbitrarily large girth and chromatic number. We study the extension of this for generalized chromatic numbers.

Recommendations

• On regular hypergraphs with high girth and high chromatic number
• Subgraphs of Kneser graphs with large girth and large chromatic number
• Triangle-free subgraphs with large fractional chromatic number
• Almost all graphs with high girth and suitable density have high chromatic number
• Digraph girth via chromatic number

Cited in

(8)

• Improper colouring of (random) unit disk graphs
• Almost all graphs with high girth and suitable density have high chromatic number
• On vertex Ramsey graphs with forbidden subgraphs
• Graphs of large chromatic number
• Subgraphs of Kneser graphs with large girth and large chromatic number
• Co-2-plex vertex partitions
• Coloring, location and domination of corona graphs
• Proof pearl: a probabilistic proof for the girth-chromatic number theorem

This page was built for publication: A note on generalized chromatic number and generalized girth

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