Triangle-free graphs with large chromatic numbers
From MaRDI portal
It is shown that there are two positive constants \(c_1, c_2\) such that the maximum possible chromatic number of a triangle-free graph with \(m>1\) edges is at most \(c_1m^{1/3}/(\log m)^{2/3}\) and at least \(c_2m^{1/3}/(\log m)^{2/3}\). This settles a problem of Erdős.
Recommendations
Cited in
(48)- Degree sequences in triangle-free graphs
- On the chromatic number of triangle-free graphs of large minimum degree
- Coloring triangle-free graphs with fixed size
- Triangle-free graphs and forbidden subgraphs
- A 4-colour problem for dense triangle-free graphs
- On the chromatic index of join graphs and triangle-free graphs with large maximum degree
- Triangle-free graphs with large independent domination number
- Dense induced bipartite subgraphs in triangle-free graphs
- Structure and colour in triangle-free graphs
- Extremal triangle-free and odd-cycle-free colourings of uncountable graphs
- A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number
- On existentially complete triangle-free graphs
- On some graph classes related to perfect graphs: a survey
- Bipartite induced density in triangle-free graphs
- Triangle-free graphs of tree-width \(t\) are \(\lceil (t+3)/2 \rceil\)-colorable
- Circumference, chromatic number and online coloring
- On the abstract chromatic number and its computability for finitely axiomatizable theories
- Triangle-free graphs without forbidden subgraphs
- The number of the maximal triangle-free graphs
- scientific article; zbMATH DE number 4130414 (Why is no real title available?)
- Some results on chromatic number as a function of triangle count
- A Construction of Graphs without Triangles having Pre-Assigned Order and Chromatic Number
- Circular chromatic number of triangle free graphs with given maximum average degree, extended abstract
- Local clique covering of claw-free graphs
- scientific article; zbMATH DE number 3900798 (Why is no real title available?)
- Triangle-free intersection graphs of line segments with large chromatic number
- scientific article; zbMATH DE number 653253 (Why is no real title available?)
- scientific article; zbMATH DE number 1076145 (Why is no real title available?)
- Triangle-Free Graphs with Large Degree
- Color class sizes of triangle-free graphs
- On degree sums of a triangle-free graph
- scientific article; zbMATH DE number 1870232 (Why is no real title available?)
- Properties of Descartes' Construction of Triangle-Free Graphs with High Chromatic Number
- The -Ramsey problem for triangle-free graphs
- On minimal triangle-free 6-chromatic graphs
- Color stable graphs
- scientific article; zbMATH DE number 5199085 (Why is no real title available?)
- scientific article; zbMATH DE number 2191978 (Why is no real title available?)
- On the maximal triangle-free edge-chromatic graphs in three colors
- scientific article; zbMATH DE number 2369587 (Why is no real title available?)
- Triangle-free subgraphs with large fractional chromatic number
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
- Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
- Counting colorings of triangle-free graphs
- Triangle Ramsey numbers of complete graphs
- A note on generalized pentagons
- The chromatic gap and its extremes
- On the chromatic index of multigraphs without large triangles
This page was built for publication: Triangle-free graphs with large chromatic numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1969797)
