Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be maximal such that, if a graph has the property that every subgraph on vertices is the union of a graph with chromatic number and a graph with edges, then has chromatic number .
Is it true that ? More generally, is ?
Source: erdosproblems.com/1092
An accepted solution exists. The statement is false.
The site labels the problem DISPROVED (LEAN), crediting Rödl's construction of nearly bipartite graphs of large chromatic number [Ro82] as noted in the thread; the Lean behind the qualifier is described under Formalization. The accepted claim is Rödl's nearly bipartite graphs, which answers both questions in the negative with the subgraph condition read, as the statement writes it, as chromatic number .