CEU Electronic Theses and Dissertations, 2008
| Author | Palmer, Cory Thomas |
|---|---|
| Title | Edge-weightings and the chromatic number |
| Summary | Motivated by the difficulty of determining bounds on the chromatic number of a graph, we examine several new graph parameters that are related to the standard chromatic number. These parameters are based on edge-weightings and are interesting in their own right but they also have potential consequences for the chromatic number. The core of the thesis will be dedicated to the particular problem to determine the minimum number of weights needed to assign to the edges of a graph $G$ with no component $K_2$ so that any two adjacent vertices have distinct sets of weights on their incident edges. The main result is that this minimum is at most $\lceil \log_2 \chi(G) \rceil+1$. This upper-bound is best possible for $\chi(G) \geq 3$. We also characterize the case when $\chi(G) = 2$. |
| Supervisor | Gyori, Ervin |
| Department | Mathematics PhD |
| Full text | https://www.etd.ceu.edu/2008/tphpac01.pdf |
Visit the CEU Library.
© 2007-2021, Central European University