• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 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

Graph marking game and graph colouring game

Wu, Jiaojiao 14 June 2005 (has links)
This thesis discusses graph marking game and graph colouring game. Suppose G=(V, E) is a graph. A marking game on G is played by two players, Alice and Bob, with Alice playing first. At the start of the game all vertices are unmarked. A play by either player consists of marking an unmarked vertex. The game ends when all vertices are marked. For each vertex v of G, write t(v)=j if v is marked at the jth step. Let s(v) denote the number of neighbours u of v for which t(u) < t(v), i.e., u is marked before v. The score of the game is $$s = 1+ max_{v in V} s(v).$$ Alice's goal is to minimize the score, while Bob's goal is to maximize it. The game colouring number colg(G) of G is the least s such that Alice has a strategy that results in a score at most s. Suppose r geq 1, d geq 0 are integers. In an (r, d)-relaxed colouring game of G, two players, Alice and Bob, take turns colouring the vertices of G with colours from a set X of r colours, with Alice having the first move. A colour i is legal for an uncoloured vertex x (at a certain step) if after colouring x with colour i, the subgraph induced by vertices of colour i has maximum degree at most d. Each player can only colour an uncoloured vertex with a legal colour. Alice's goal is to have all the vertices coloured, and Bob's goal is the opposite: to have an uncoloured vertex without legal colour. The d-relaxed game chromatic number of a graph G, denoted by $chi_g^{(d)}(G)$ is the least number r so that when playing the (r, d)-relaxed colouring game on G, Alice has a winning strategy. If d=0, then the parameter is called the game chromatic number of G and is also denoted by $chi_g(G)$. This thesis obtains upper and lower bounds for the game colouring number and relaxed game chromatic number of various classes of graphs. Let colg(PT_k) and colg(P) denote the maximum game colouring number of partial k trees and the maximum game colouring number of planar graphs, respectively. In this thesis, we prove that colg(PT_k) = 3k+2 and colg(P) geq 11. We also prove that the game colouring number colg(G) of a graph is a monotone parameter, i.e., if H is a subgraph of G, then colg(H) leq colg(G). For relaxed game chromatic number of graphs, this thesis proves that if G is an outerplanar graph, then $chi_g^{(d)}(G) leq 7-t$ for $t= 2, 3, 4$, for $d geq t$, and $chi_g^{(d)}(G) leq 2$ for $d geq 6$. In particular, the maximum $4$-relaxed game chromatic number of outerplanar graphs is equal to $3$. If $G$ is a tree then $chi_ g^{(d)}(G) leq 2$ for $d geq 2$.

Page generated in 0.1074 seconds