On the colorability of \(m\)-composed graphs (Q1336697): Difference between revisions

A graph is said to be \(m\)-degenerated if each of its subgraphs has the minimum degree at most \(m\). If a graph is the union of an \(m\)-degenerated graph and an acyclic graph, then it is called \(m\)-composed. This paper provides a conjecture that any \(m\)-composed graph is \(k\)-colorable, where \(k= m+1+\) the integral part of the half of \(1+ \sqrt{8m+1}\). In support of this, many \((k+1)\)-chromatic graphs are shown not to be \(m\)-composed.