• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

The Oriented Colourings of Bipartite Graphs

Wu, Yu-feng 25 July 2006 (has links)
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).

Page generated in 0.3084 seconds