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.046zbMATH Open1162.05020arXiv1308.3046OpenAlexW2056034021MaRDI QIDQ998482FDOQ998482

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)

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*2,2*(k-3),1}$, $K_{3,2*(k-1)}$, $K_{s+3,2*(k-s-1),1*s}$, $K_{4,3,2*(k-4),1*2}$, and $K_{5,3,2*(k-5),1*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*3,2*(k-5),1*2})=k$ and $Ch(K_{4,3*2,2*(k-6),1*3})=k$ (for $kgeq5$ and $kgeq6$, respectively).

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

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

zbMATH Keywords

list coloringcomplete multipartite graphsOhba's conjecturechromatic choosable graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Some upper bounds on the total and list chromatic numbers of multigraphs
• Choice number of some complete multi-partite graphs
• On the choosability of complete multipartite graphs with part size three
• On choosability of some complete multipartite graphs and Ohba's conjecture
• List colourings of graphs
• Title not available (Why is that?)
• On chromatic‐choosable graphs
• Chromatic choosability of a class of complete multipartite graphs
• Title not available (Why is that?)
• The list chromatic index of a bipartite multigraph
• Title not available (Why is that?)

Cited In (10)

• 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
• Choice number of some complete multi-partite graphs
• Chromatic choosability of a class of complete multipartite graphs
• On choosability of complete multipartite graphs \(K_{4,3*t,2*(k-2t-2),1*(t+1)}\)
• The choice number of \(K(4,2,\dots,2)\) -- a dispute resolved
• Title not available (Why is that?)
• 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)