Ohba's conjecture for graphs with independence number five

DOI10.1016/j.disc.2011.02.026zbMath1223.05077WikidataQ123009835 ScholiaQ123009835MaRDI QIDQ536225

Alexandr V. Kostochka, Douglas R. Woodall, Michael Stiebitz

Publication date: 16 May 2011

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2011.02.026

zbMATH Keywords

chromatic number; vertex coloring; choosability; list chromatic number; complete multipartite graph; list coloring

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C15: Coloring of graphs and hypergraphs

Related Items

A Proof of a Conjecture of Ohba, Ohba's conjecture is true for graphs \(K_{t+2,3,2\ast(k-t-2),1\ast t}\), Beyond Ohba's conjecture: a bound on the choice number of \(k\)-chromatic graphs with \(n\) vertices, Towards a version of Ohba's conjecture for improper colorings

Cites Work

• List colouring when the chromatic number is close to the order of the graph
• Choice number of complete multipartite graphs \(K_{3*3,2*(k - 5),1*2}\) and \(K_{4,3*2,2*(k - 6),1*3}\)
• Ohba's conjecture is true for graphs with independence number at most three
• Choice number of some complete multi-partite graphs
• On choosability of some complete multipartite graphs and Ohba's conjecture
• On chromatic‐choosable graphs
• On Representatives of Subsets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item