Properties of Descartes' Construction of Triangle-Free Graphs with High Chromatic Number

DOI10.1017/S0963548399004022MaRDI QIDQ4934785zbMATH OpenFDO

Authors J. Nešetřil, Alexandr Kostochka

Publication date 30 January 2000

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0963548399004022

zbMATH Keywords

girthhypergraphscolour-critical graphshigh chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• A Construction of Graphs without Triangles having Pre-Assigned Order and Chromatic Number
• Critical graphs without triangles: an optimum density construction
• Triangle-free graphs with large chromatic numbers
• A hypergraph-free construction of highly chromatic graphs without short cycles

Cited in

(10)

• On a construction of graphs with high chromatic capacity and large girth
• High girth hypergraphs with unavoidable monochromatic or rainbow edges
• Adding edges to increase the chromatic number of a graph
• Coloring, sparseness and girth
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• Girth and λ \lambda ‐choosability of graphs
• Box and Segment Intersection Graphs with Large Girth and Chromatic Number
• Triangle-free graphs of tree-width \(t\) are \(\lceil (t+3)/2 \rceil\)-colorable
• Geometric Graphs with Exponential Chromatic Number and Arbitrary Girth
• Monochromatic graph decompositions inspired by anti-Ramsey colorings

This page was built for publication: Properties of Descartes' Construction of Triangle-Free Graphs with High Chromatic Number

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