A graph G is said to be chromatic-choosable if ch(G) = χ(G). Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. It is clear that Ohba's conjecture is true if and only if it is true for complete multipartite graphs. In this paper we show that Ohba's conjecture is true for complete multipartite graphs $K_{4,3*t,2*(k-2t-2),1*(t+1)}$ for all integers t ≥ 1 and k ≥ 2t+2, that is, $ch(K_{4,3*t,2*(k-2t-2),1*(t+1)}) = k$, which extends the results $ch(K_{4,3,2*(k-4),1*2}) = k$ given by Shen et al. (Discrete Math. 308 (2008) 136-143), and $ch(K_{4,3*2,2*(k-6),1*3}) = k$ given by He et al. (Discrete Math. 308 (2008) 5871-5877).
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In the paper, we show that the incidence chromatic number χi of a complete k-partite graph is at most Δ + 2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to Δ + 1 if and only if the smallest part has only one vertex (i.e., Δ = n − 1). Formally, for a complete k-partite graph G = Kr1,r2,...,rk with the size of the smallest part equal to r1 ≥ 1 we have χi(G)={Δ(G)+1if r1=1,Δ(G)+2if r1>1. $$\chi _i (G) = \left\{ {\matrix{{\Delta (G) + 1} & {{\rm{if}}\;r_1 = 1,} \cr {\Delta (G) + 2} & {{\rm{if}}\;r_1 > 1.} \cr } } \right.$$ In the paper we prove that the incidence 4-coloring problem for semicubic bipartite graphs is 𝒩𝒫-complete, thus we prove also the 𝒩𝒫-completeness of L(1, 1)-labeling problem for semicubic bipartite graphs. Moreover, we observe that the incidence 4-coloring problem is 𝒩𝒫-complete for cubic graphs, which was proved in the paper [12] (in terms of generalized dominating sets).
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.