Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Improved upper bounds for nearly antipodal chromatic number of paths

100%

Shen Y.-F., Zheng G.-P., He W.-J.

Discussiones Mathematicae Graph Theory

2007

tom 27

nr 1

159-174

For paths Pₙ, G. Chartrand, L. Nebeský and P. Zhang showed that $ac'(Pₙ) ≤ \binom{n-2}{2} + 2$ for every positive integer n, where ac'(Pₙ) denotes the nearly antipodal chromatic number of Pₙ. In this paper we show that $ac'(Pₙ) ≤ \binom{n-2}{2} - n/2 - ⎣10/n⎦ + 7$ if n is even positive integer and n ≥ 10, and $ac'(Pₙ) ≤ \binom{n-2}{2} - (n-1)/2 - ⎣13/n⎦ + 8$ if n is odd positive integer and n ≥ 13. For all even positive integers n ≥ 10 and all odd positive integers n ≥ 13, these results improve the upper bounds for nearly antipodal chromatic number of Pₙ.

On choosability of complete multipartite graphs $K_{4,3t,2(k-2t-2),1*(t+1)}$

100%

Zheng G.-P., Shen Y.-F., Chen Z.-L., Lv J.-F.

Discussiones Mathematicae Graph Theory

2010

tom 30

nr 2

237-244

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).

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Shen Y.-F.

2 Zheng G.-P.

1 Chen Z.-L.

1 He W.-J.

1 Lv J.-F.

1 2010

1 2007

Wyniki wyszukiwania

Improved upper bounds for nearly antipodal chromatic number of paths

On choosability of complete multipartite graphs $K_{4,3t,2(k-2t-2),1*(t+1)}$

Ograniczanie wyników

Wyniki wyszukiwania

Improved upper bounds for nearly antipodal chromatic number of paths

On choosability of complete multipartite graphs $K_{4,3*t,2*(k-2t-2),1*(t+1)}$

On choosability of complete multipartite graphs $K_{4,3t,2(k-2t-2),1*(t+1)}$