臺灣博碩士論文加值系統

令S是一個包含k個不同元素的集合。若一個函數f從V(D)對應到S使得(i)如果xy是D上的一條定向邊，則f(x)≠f(y)，及(ii)如果xy和zt是D上的兩條定向邊以及f(x)=f(t)，則f(y)≠f(z)；則此f稱為一個定向圖D上的一個定向k著色。在一個定向圖D上，若存在一個定向k著色且k是最小，則此k即為D的定向著色數，記為Xo(D)。令O(G)是包含無向圖G上所有定向圖的集合。若D是O(G)的一個元素且使得Xo(D)為最大，則此Xo(D)即為G的定向著色數，記為Xo(G)。在這篇文章中，我們討論了完全二部圖和完全k部圖的定向著色數。令一個格子圖G(m,n)的點集合為V(G(m,n))={(i,j)|1≦i≦m,1≦j≦n} 且邊集合為 E(G(m,n))={(i,j)(x,y) | (i=x+1 and j=y) or (i=x
and j=y+1)}。 Fertin，Raspaud 和 Roychowdhury [3] 利用電腦程式證明Xo(G(4,5))≧7。在此，我們給予一個G(5,6)上的某個定向圖D(5,6)，使得Xo(D(5,6)}=7的一個證明。

Let S be a set of k distinct elements. An oriented k coloring of an oriented graph D is a mapping f:V(D)→S such that (i) if xy is conatined in A(D), then f(x)≠f(y) and (ii) if xy,zt are conatined in
A(D) and f(x)=f(t), then f(y)≠f(z). The oriented chromatic
number Xo(D) of an oriented graph D is defined as the minimum
k where there exists an oriented k-coloring of D. For an undirected
graph G, let O(G) be the set of all orientations D of G. We
define the oriented chromatic number Xo(G) of G to be the
maximum of Xo(D) over D conatined by O(G). In this thesis, we
determine the oriented chromatic number of complete bipartite graphs and
complete k-partite graphs. A grid G(m,n) is a graph with the
vertex set V(G(m,n))={(i,j) | 1≦i≦m,1≦j≦n} and the edge
set E(G(m,n))={(i,j)(x,y) | (i=x+1 and j=y) or (i=x and j=y+1)}. Fertin, Raspaud and Roychowdhury [3] proved Xo(G(4,5))≧7 by computer programs. Here, we give a proof of
Xo(D(5,6)=7 where D(5,6) is the orientation of
G(5,6).

1 Introduction 2
2 Previous results 4
3 The main results 7
4 Conclusion 16

[1] O.V. Borodin, A.V. Kostochka, J. Neˇsetˇril, A. Raspaud, E. Sopena, On the maximum
average degree and the oriented chromatic number of a graph, Discrete Math.
206 (1999) 77-89.
[2] B.Courcelle. The monadic second order logic of graphs VI: On several representations
of graphs by relational structures, Discrete Applied Math. 54 (1994), 117-149.
[3] G. Fertin, A. Raspaud, A. Roychowdhury, On the oriented chromatic number of
grids, Inf. Process. Lett. 85 (2003) 261-266.
[4] A.V. Kostochka, E. Sopena, X. Zhu, Acyclic and oriented chromatic number of
graphs, J. Graph Theory 24 (4) (1997) 331-340.
[5] P. Ochem, Oriented colorings of triangle-free planar graphs, Inf. Process. Lett. 92
(2004) 71-76.
[6] A. Raspaud and E. Sopena, Good and semi-strong colorings of oriented planar
graphs, Inf. Process. Lett. 51 (1994), 171-174.
[7] E. Sopena, The chromatic number of oriented graphs, J. Graph Theory 25 (1997)
191-205.
[8] E. Sopena, There exist oriented planar graphs with oriented chromatic number at
least sixteen, Inf. Process. Lett. 81 (6) (2002) 309-312.
[9] A. Szepietowski, M, Targan. A note on the oriented chromatic number of grids, Inf.
Process. Lett. 92 (2004) 65-70.