Choice number of complete multipartite graphs K₃*3,2*(k - 5),1*2 and K₄,3*2,2*(k - 6),1*3

DOI10.1016/J.DISC.2007.10.046MaRDI QIDQ998482zbMATH OpenOpenAlexFDO

Authors Wenjie He, Lingmin Zhang, Daniel W. Cranston, Yufa Shen, Guoping Zheng

Publication date 28 January 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.3046

zbMATH Keywords

list coloringcomplete multipartite graphsOhba's conjecturechromatic choosable graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A graph $G$ is called emph{chromatic-choosable} if its choice number is equal to its chromatic number, namely $Ch(G)=chi(G)$. Ohba has conjectured that every graph $G$ satisfying $|V(G)|leq2chi(G)+1$ is chromatic-choosable. Since each $k$-chromatic graph is a subgraph of a complete $k$-partite graph, we see that Ohba's conjecture is true if and only if it is true for every complete multipartite graph. However, the only complete multipartite graphs for which Ohba's conjecture has been verified are: $K_{3\ast 2,2\ast (k-3),1}$, $K_{3,2\ast (k-1)}$, $K_{s+3,2\ast (k-s-1),1\ast s}$, $K_{4,3,2\ast (k-4),1\ast 2}$, and $K_{5,3,2\ast (k-5),1\ast 3}$. In this paper, we show that Ohba's conjecture is true for two new classes of complete multipartite graphs: graphs with three parts of size 3 and graphs with one part of size 4 and two parts of size 3. Namely, we prove that $Ch(K_{3\ast 3,2\ast (k-5),1\ast 2})=k$ and $Ch(K_{4,3\ast 2,2\ast (k-6),1\ast 3})=k$ (for $kgeq5$ and $kgeq6$, respectively).

Recommendations

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

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
• 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
• Some upper bounds on the total and list chromatic numbers of multigraphs
• The list chromatic index of a bipartite multigraph

Cited in

(12)

• Ohba's conjecture is true for graphs \(K_{t+2,3,2\ast(k-t-2),1\ast t}\)
• Ohba's conjecture for graphs with independence number five
• On (k, k n - k^2 - 2 k - 1)-choosability of n-vertex graphs
• Ohba's conjecture is true for graphs with independence number at most three
• On the choosability of some graphs
• Estimates of the choice numbers and the Ohba numbers of some complete multipartite graphs.
• Choice number of some complete multi-partite graphs
• On choosability of complete multipartite graphs \(K_{4,3*t,2*(k-2t-2),1*(t+1)}\)
• Chromatic choosability of a class of complete multipartite graphs
• The choice number of \(K(4,2,\dots,2)\) -- a dispute resolved
• scientific article; zbMATH DE number 7296014 (Why is no real title available?)
• Multiple list coloring of 3‐choice critical graphs

This page was built for publication: Choice number of complete multipartite graphs \(K_{3*3,2*(k - 5),1*2}\) and \(K_{4,3*2,2*(k - 6),1*3}\)

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