On the colorability of m-composed graphs

DOI10.1016/0012-365X(94)90025-6MaRDI QIDQ1336697zbMATH OpenOpenAlexFDO

Authors R. Klein

Publication date 20 March 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(94)90025-6

zbMATH Keywords

\(m\)-composed graph\(m\)-degenerated graphcolorabilitygraph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 825142
• scientific article; zbMATH DE number 653253
• scientific article; zbMATH DE number 819126
• scientific article; zbMATH DE number 889958
• Some bounds on the generalised total chromatic number of degenerate graphs

Cites work

• Colour-critical graphs and hypergraphs
• scientific article; zbMATH DE number 3241107 (Why is no real title available?)
• Nowhere-zero 6-flows

Cited in

(3)

• scientific article; zbMATH DE number 1303029 (Why is no real title available?)
• scientific article; zbMATH DE number 819126 (Why is no real title available?)
• scientific article; zbMATH DE number 825142 (Why is no real title available?)

This page was built for publication: On the colorability of \(m\)-composed graphs

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