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).
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0725106-232541 |
| Date | 25 July 2006 |
| Creators | Wu, Yu-feng |
| Contributors | Li-Da Tong, none, none, none, none |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0725106-232541 |
| Rights | withheld, Copyright information available at source archive |
Page generated in 0.002 seconds