Ohba's conjecture is true for graphs with independence number at most three

DOI10.1016/J.AML.2009.01.001MaRDI QIDQ1023085zbMATH OpenOpenAlexWikidataFDO

Authors Wenjie He, Yanpo Li, Yufa Shen, Guoping Zheng

Publication date 10 June 2009

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.aml.2009.01.001

zbMATH Keywords

list coloringcomplete multipartite graphsindependence numberOhba's conjecturechromatic-choosable

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Ohba's conjecture for graphs with independence number five
• Ohba's conjecture is true for graphs \(K_{t+2,3,2\ast(k-t-2),1\ast t}\)
• Chromatic choosability of a class of complete multipartite graphs
• On choosability of some complete multipartite graphs and Ohba's conjecture
• Choice number of complete multipartite graphs \(K_{3*3,2*(k - 5),1*2}\) and \(K_{4,3*2,2*(k - 6),1*3}\)

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 1123764 (Why is no real title available?)
• scientific article; zbMATH DE number 2192112 (Why is no real title available?)
• Choice number of some complete multi-partite graphs
• Chromatic choosability of a class of complete multipartite graphs
• Graph colorings with local constraints -- a survey
• List colouring when the chromatic number is close to the order of the graph
• List colourings of graphs
• Multicriterial graph problems with MAXMIN criterion
• On choosability of some complete multipartite graphs and Ohba's conjecture
• On chromatic‐choosable graphs
• On the choosability of complete multipartite graphs with part size three

Cited in

(10)

• On chromatic‐choosable graphs
• Application of polynomial method to on-line list colouring of graphs
• Ohba's conjecture is true for graphs \(K_{t+2,3,2\ast(k-t-2),1\ast t}\)
• Towards an on-line version of Ohba's conjecture
• Ohba's conjecture for graphs with independence number five
• On the choosability of some graphs
• Chromatic-choosability of hypergraphs with high chromatic number
• Chromatic choosability of a class of complete multipartite graphs
• Beyond Ohba's conjecture: a bound on the choice number of \(k\)-chromatic graphs with \(n\) vertices
• A proof of a conjecture of Ohba

This page was built for publication: Ohba's conjecture is true for graphs with independence number at most three

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