1 |
Game Colourings of GraphsChang, Hung-yung 09 August 2007 (has links)
A graph function $f$ is a mapping which assigns each graph $H$
a positive integer $f(H)
leq |V(H)|$ such that $f(H)=f(H')$ if $H$ and $H'$ are
isomorphic. Given a graph function $f$ and a graph $G$, an
$f$-colouring of $G$ is a mapping $c: V(G) o
mathbb{N}$ such that every subgraph $H$ of $G$ receives at least
$f(H)$ colours, i.e., $|c(H)| geq f(H)$. The $f$-chromatic
number, $chi(f,G)$, is the minimum number of colours used in an
$f$-colouring of $G$. The $f$-chromatic number of a graph is a
natural generalization of the chromatic number of a graph
introduced by Nev{s}etv{r}il and Ossena de Mendez. Intuitively,
we would like to colour the vertices of a graph $G$ with minimum
number of colours subject to the constraint that the number of
colours assigned to certain subgraphs must be large enough. The
original chromatic number of a graph and many of its
generalizations are of this nature. For example, the chromatic
number of a graph is the least number of colours needed to colour
the vertices of the graph so that any subgraph isomorphic to
$K_2$ receives $2$ colours. Acyclic chromatic number of a graph is
the least number of colours needed to colour the vertices of the
graph so that any subgraph isomorphic to $K_2$ receives $2$
colours, and each cycle receives at least $3$ colours.
This thesis studies the game version of $f$-colouring of graphs.
Suppose $G$ is a graph and $X$ is a set of colours. Two players,
Alice and Bob, take turns colour the vertices of $G$ with colours
from the set $X$. A partial colouring of $G$ is legal (with respect
to graph function $f$) if for any subgraph $H$ of $G$, the sum of
the number of colours used in $H$ and the number of uncoloured
vertices of $H$ is at least $f(H)$. Both Alice and Bob must colour
legally (i.e., the partial colouring produced needs to be legal).
The game ends if either all the vertices are coloured or there are
uncoloured vertices but there is no legal colour for any of the
uncoloured vertices. In the former case, Alice wins the game. In the
latter case, Bob wins the game. The $f$-game chromatic number of
$G$, $chi_g(f, G)$, is the least number of colours that the colour
set $X$ needs to contain so that Alice has a winning strategy.
Observe that if $|X| = |V(G)|$, then Alice always wins. So the
parameter $chi_g(f,G)$ is well-defined. We define the $f$-game
chromatic index on a graph $G$, $chi'(f,G)$, to be the $f$-game
chromatic number on the line graph of $G$.
A natural problem concerning the $f$-game chromatic number of graphs
is for which graph functions $f$, the $f$-game chromatic number of
$G$ is bounded by a constant for graphs $G$ from some natural
classes of graphs. In case the $f$-game chromatic number of a class
${cal K}$ of graphs is bounded by a constant, one would like to
find the smallest such constant. This thesis studies the $f$-game
chromatic number or index for some special classes of graphs and for
some special graph functions $f$. The graph functions $f$ considered
are the following graph functions:
1. The $d$-relaxed function, ${
m Rel}_d$, is defined as ${
m Rel}_d(K_{1,d+1})=2$ and ${
m Rel}_d(H)=1$ otherwise.
2. The acyclic function, ${
m Acy}$, is defined as ${
m Acy}(K_2)=2$ and ${
m Acy}(C_n)=3$ for any $n geq 3$ and
${
m Acy}(H)=1$ otherwise.
3. The $i$-path function, ${
m Path}_i$, is defined as ${
m Path}_i(K_2)=2$ and
${
m Path}_i(P_i)=3$ and ${
m Path}_i(H)=1$ otherwise, where $P_i$
is the path on $i$ vertices.
The classes of graphs considered in the thesis are outerplanar
graphs, forests and the line graphs of $d$-degenerate graphs. In
Chapter 2, we discuss the acyclic game chromatic number of
outerplanar graphs. It is proved that for any outerplanar graph $G$,
$chi_g({
m Acy},G) leq 7$. On the other hand, there is an
outerplanar graph $G$ for which $chi_g({
m Acy},G) = 6$. So the
best upper bound for $chi_g({
m Acy},G)$ for outerplanar graphs is
either $6$ or $7$. Moreover, we show that for any integer $n$, there
is a series-parallel graph $G_n$ with $chi_g({
m Acy}, G_n)
> n$.
In Chapter 3, we discuss the ${
m Path}_i$-game chromatic number
for forests. It is proved that if $i geq 8$, then for any forest
$F$, $chi_g({
m Path}_i, F) leq 9$. On the other hand, if $i
leq 6$, then for any integer $k$, there is a tree $T$ such that
$chi_g({
m Path}_i, T) geq k$.
Chapter 4 studies the $d$-relaxed game chromatic indexes of
$k$-degenerated graphs. It is proved that if $d geq 2k^2 + 5k-1$
and $G$ is $k$-degenerated, then $chi'_{
m g}({
m Rel}_d,G)
leq 2k + frac{(Delta(G)+k-1)(k+1)}{d-2k^2-4k+2}$. On the other hand,
for any positive integer $ d leq Delta-2$, there is a tree $T$
with maximum degree $Delta$ for which $chi'_g({
m Rel}_d, T)
geq frac{2Delta}{d+3}$. Moreover, we show that $chi'_g({
m Rel}_d, G) leq
2$ if $d geq 2k + 2lfloor frac{Delta(G)-k}{2}
floor +1$ and
$G$ is a $k$-degenerated graph.
|
2 |
Circular chromatic indexes of generalized necklacesJhan, Wen-min 15 July 2005 (has links)
Suppose $G$ is a graph and $e=ab$ is an edge of $G$. For a
positive integer $k$, the $G$-necklace of length $k$ (with respect
to edge $e$), denoted by $N_k(G)$, is the graph constructed as
follows: Take the vertex disjoint union of $k$ copies of $G$, say
$Q_1 cup Q_2 cup cdots cup Q_k$, where each $Q_i$ is a copy of
$G$, with $e_i=a_ib_i$ be the copy of $e=a b$ in $Q_i$. Add a
vertex $u$, delete the edges $e_i$ for $i=1, 2, cdots, k$ and
add edges: $ua_1, b_1a_2, b_2a_3, cdots, b_{k-1}a_k, b_ku$. This
thesis determines the circular chromatic indexes of $G$-necklaces
for $G = K_{2n}$ and $G= K_{m, m}$.(¨£¹q¤l½×¤å²Ä¤»¶)
|
3 |
The Oriented Colourings of Bipartite GraphsWu, 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).
|
4 |
The upper chromatic number and chromatic polynomials of some mixed hypergraphs林妤芬 Unknown Date (has links)
本文分為兩章. 第一章先介紹sieve-number(即s(H)) ,並將所有mixed hypergraph的最大著色數能用n-s(H)的圖形條件限制出來.再討論能用s(H)表示其最大著色數的圖形. 第二章主要是討論interval mixed hypergraph的著色方程式.
|
5 |
Chromatic Polynomials and Orbital Chromatic Polynomials and their RootsOrtiz, Jazmin 01 January 2015 (has links)
The chromatic polynomial of a graph, is a polynomial that when evaluated at a positive integer k, is the number of proper k colorings of the graph. We can then find the orbital chromatic polynomial of a graph and a group of automorphisms of the graph, which is a polynomial whose value at a positive integer k is the number of orbits of k-colorings of a graph when acted upon by the group. By considering the roots of the orbital chromatic and chromatic polynomials, the similarities and differences of these polynomials is studied. Specifically we work toward proving a conjecture concerning the gap between the real roots of the chromatic polynomial and the real roots of the orbital chromatic polynomial.
|
6 |
Graph marking game and graph colouring gameWu, 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$.
|
7 |
The Irish harp in art music c1550-c1650Robson, Tristram Newton Fatkin January 1997 (has links)
The sixteenth century brought increased English military occupation and settlement to Ireland. Members of the invading nobility, who consequently came into contact with the native culture, were seduced by the sound of the Irish harp and took the instrument from its roots in Gaelic society and placed it in the setting of European courtly music. My aim is to examine this process, the resulting developments which took place in the evolution of the Irish harp, and compositions associated with its usage in the 'art' music of England and the Continent. Particular reference is made to the 'Harpe' Consorts of William Lawes together with their sources and resulting implications when considering the capabilities of the instrument employed. The harp's role within this music is also analysed and a complete set of transcriptions of Lawes' consorts is included. Works by other musicians associated with the Irish harp during the period 1550-1650 are also discussed with specific reference to the compasses and accidentals of the instruments required by the composers where appropriate. Transcriptions of works attributed to Cormack MacDermott and the anonymous harp parts located at the back of Ch Ch Mus MS 5 are included. Martin Peerson's 'Mottects or Grave Chamber Music' and a collection of works for 'Treble Bass Viol and Harp', included in the back of the 1687 edition of Christopher Simpson's A Compendium of Practical Music are also discussed. A major part of the research involved the reconstruction of an Irish chromatic harp (presented as part of this thesis) capable of playing the music examined. An account of this is given in a report which looks at the decisions and processes involved, difficulties encountered, as well as some recommendations for future experimental directions.
|
8 |
Chromatic polynomials of mixed graphsWheeler, Mackenzie J. 27 August 2019 (has links)
Let G = (V,A,E) be a mixed graph and co : V → {1, 2,...,λ} a function such that co is a proper colouring of the underlying graph, Und(G), and co(u) ≠ co(y) when co(v) = co(x), for every pair of arcs (u,v) and (x,y). Such a function is called a proper oriented λ − colouring of G. The number of proper oriented λ–colourings of G, denoted fo(G,λ), is a polynomial in λ. We call fo(G,λ) the mixed-chromatic polynomial of G. In this thesis we will first present the basic theory of the mixed-chromatic poly-nomial. This theory will include computational tools and results concerning the coefficients of fo(G,λ). Next, we will consider the question of chromatic uniqueness and invariance of mixed graphs. Lastly, we reformulate a contract-delete recurrence for chromatic polynomials in order to enumerate various colourings, such as k−frugal λ−colourings. / Graduate
|
9 |
Chip Firing and Fractional Chromatic Number of the Kneser GraphLiao, Shih-kai 29 June 2004 (has links)
In this thesis we focus on the investigation of the relation between the the chip-firing and fractional coloring. Since chi_{f}(G)=inf {n/k : G is homomorphic to K(n,k)}, we find that G has an (n,k)-periodic sequence for some configuration if and only if G is homomorphic to
K(n,k). Then we study the periodic configurations for the Kneser graphs. Finally, we try to evaluate the number of chips of the periodic configurations for K(n,k).
|
10 |
Circular chromatic number of Kneser GraphsHsieh, Chin-chih 05 July 2004 (has links)
This thesis studies the circular chromatic number of Kneser
graphs. It was known that if m is
greater than 2n^{2}(n-1), then the Kneser graph KG(m,n) has its circular chromatic number
equal its chromatic number . In particular, if
n = 3, then KG(m,3) has its circular chromatic number equal its
chromatic number when m is greater than 36. In this thesis, we improve
this result by proving that if m is
greaer than 24, then chi_c(KG(m,3)) = chi(KG(m,3)).
|
Page generated in 0.0405 seconds