On choosability of some complete multipartite graphs and Ohba's conjecture
A graph \(G\) with chromatic number \(k=\chi(G)\) is called chromatic-choosable if the vertices of \(G\) can always be colored from lists of size \(k\). Ohba conjectured that if \(G\) has at most \(2k+1\) vertices, then it is chromatic-choosable. It suffices to verify this conjecture for complete \(k\)-partite graphs on \(2k+1\) vertices, and those graphs are entirely determined by their ``large parts (parts on more than 2 vertices.) So far Ohba's conjecture has been verified in the cases when there is only one large part, or when there are two large parts, both of size 3. In this paper Ohba's conjecture is verified for the case when there are only two large parts, one of size 3 and the other of size 4 or 5.
- On the Choice Numbers of Some Complete Multipartite Graphs
- Estimates of the choice numbers and the Ohba numbers of some complete multipartite graphs.
- Choosability with separation of complete multipartite graphs and hypergraphs
- Choice number of some complete multi-partite graphs
- Chromatic choosability of a class of complete multipartite graphs
- On the choosability of complete multipartite graphs with part size three
- On the choosability of some graphs
- On a theorem of Erdős, Rubin, and Taylor on choosability of complete bipartite graphs
- On choosability of complete multipartite graphs \(K_{4,3*t,2*(k-2t-2),1*(t+1)}\)
- On the asymptotic value of the choice number of complete multi‐partite graphs
- Choice number of some complete multi-partite graphs
- scientific article; zbMATH DE number 446487 (Why is no real title available?)
- 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?)
- 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 chromatic‐choosable graphs
- On the choosability of complete multipartite graphs with part size three
- Some upper bounds on the total and list chromatic numbers of multigraphs
- The list chromatic index of a bipartite multigraph
- Ohba's conjecture is true for graphs with independence number at most three
- Towards an on-line version of Ohba's conjecture
- Ohba's conjecture is true for graphs \(K_{t+2,3,2\ast(k-t-2),1\ast t}\)
- Estimates of the choice numbers and the Ohba numbers of some complete multipartite graphs.
- On choosability of complete multipartite graphs \(K_{4,3*t,2*(k-2t-2),1*(t+1)}\)
- Application of polynomial method to on-line list colouring of graphs
- On-line list colouring of complete multipartite graphs
- Beyond Ohba's conjecture: a bound on the choice number of \(k\)-chromatic graphs with \(n\) vertices
- On-line choice number of complete multipartite graphs: an algorithmic approach
- A proof of a conjecture of Ohba
- Ohba's conjecture for graphs with independence number five
- Chromatic choosability of a class of complete multipartite graphs
- scientific article; zbMATH DE number 2192112 (Why is no real title available?)
- On the asymptotic value of the choice number of complete multi‐partite graphs
- Chromatic λ‐choosable and λ‐paintable graphs
- Bad list assignments for non‐k $k$‐choosable k $k$‐chromatic graphs with 2k+2 $2k+2$‐vertices
- Chromatic-choosability of hypergraphs with high chromatic number
- Minimum non-chromatic--choosable graphs (extended abstract)
- Minimum non-chromatic-choosable graphs with given chromatic number
- On the choice number of complete multipartite graphs with part size four
- Choice number of complete multipartite graphs \(K_{3*3,2*(k - 5),1*2}\) and \(K_{4,3*2,2*(k - 6),1*3}\)
This page was built for publication: On choosability of some complete multipartite graphs and Ohba's conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2463475)
