Towards on-line Ohba's conjecture

Details Towards on-line Ohba's conjecture Towards on-line Ohba's conjecture

2011-11-23

arxiv.org/abs/1111.5458v1

Mathematics

Combinatorics

Scientific paper

Ohba conjectured that every graph $G$ with $|V(G)| \le 2 \chi(G)+1$ has its choice number equal its chromatic number. The on-line choice number of a graph is a variation of the choice number defined through a two person game, and is always at least as large as its choice number. Based on the result that for $k \ge 3$, the complete multipartite graph $K_{2\star (k-1), 3}$ is not on-line $k$-choosable, the on-line version of Ohba's conjecture is modified in [P. Huang, T. Wong and X. Zhu, Application of polynomial method to on-line colouring of graphs, European J. Combin., 2011] as follows: Every graph $G$ with $|V(G)| \le 2 \chi(G)$ has its on-line choice number equal its chromatic number. In this paper, we prove that for any graph $G$, there is an integer $n$ such that the join $G + K_n$ of $G$ and $K_n$ has its on-line choice number equal chromatic number. Then we show that the on-line version of Ohba conjecture is true if $G$ has independence number at most 3. We also present an alternative proof of the result that Ohba's conjecture is true for graphs of independence number at most 3 and an alternative proof of the following result of Kierstead: For any positive integer $k$, the complete multipartite graph $K_{3 \star k}$ has choice number $\lceil (4k-1)/3 \rceil$. Finally, we prove that the on-line choice number of $K_{3 \star k}$ is at most $(3/2)k$. The exact value of the on-line choice number of $K_{3 \star k}$ remains unknown.

Affiliated with

Also associated with

No associations

Rating

Towards on-line Ohba's conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Towards on-line Ohba's conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards on-line Ohba's conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-377045