#TITLE_ALTERNATIVE#
Two players, A and B, color the vertices of graph G choosing from the set of colors (1,2,…,K ) Player A is aiming that all vertices of G are colored, and player B is trying to prevent this. They alternate turns with A starting the game, and the only rule they must obey is to color a vertex with a...
Saved in:
| Main Author: | |
|---|---|
| Format: | Final Project |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/14594 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | Two players, A and B, color the vertices of graph G choosing from the set of colors (1,2,…,K ) Player A is aiming that all vertices of G are colored, and player B is trying to prevent this. They alternate turns with A starting the game, and the only rule they must obey is to color a vertex with a color different from all the colors appeared in its neighborhood. If all the vertices of G are colored, A wins, otherwise, B wins (that is, at a certain state of the game there appears an uncolored vertex whose neighborhood contains all colors). The smallest k such that A has a winning strategy on G using k colors is called the game chromatic number of G, along with the notation Xg(G). <br />
<br />
<br />
In this final project, it is determined the game chromatic numbers of certain classes of graphs, namely K1+Cn, n≥3, graf K1+Pn, n≥2, and a modification of P3+Pn, n≥2. Aside from that, edges subdivision operations are done to all respective graph classes. In the new graph classes, which are the results of the edges subdivision, the game chromatic numbers are also determined. |
|---|