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

colour-critical graphsgirthhigh chromatic numberhypergraphs

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

(12)

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

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)