A (k,l)-colouring of a graph is a partition of its vertex set into k independent sets and l cliques. The bichromatic number chi^b of a graph is the minimum r$ such that the graph is (k,l)-colourable for all k+l=r. The bichromatic number is related to the cochromatic number, which can also be defined in terms of (k,l)-colourings.
The bichromatic number is a fairly recent graph parameter that arises in the study of extremal graphs related to a classical result of Erd\H{o}s, Stone and Simonovits, and in the study of the edit distance of graphs from hereditary graph classes. While the cochromatic number has been well studied in the literature, there are only few known structural results for the bichromatic number. A main focus of this thesis is to establish a foundation of knowledge about the bichromatic number. The secondary focus is on $(k,l)$-colourings of certain interesting graph classes.
Two known bounds for the bichromatic number are $\chi^b \leq \chi + \theta - 1$, where $\chi$ is the chromatic number and $\theta$ the clique covering number of the graph, and $\chi^b \geq \sqrt{n}$, where $n$ the number of vertices of the graph. We give a complete characterization of all graphs for which equality holds in the first bound, and show that the second bound is best possible by constructing graphs for square numbers $n$ such that equality holds in the bound. We investigate graphs for which the bichromatic number equals the cochromatic number and prove a Brooks-type theorem for the bichromatic number.
Regarding $(k,l)$-colourings, we find a new algorithm for calculating the $(k,l)$-colourability of cographs and show that cographs have a particularly nice representation with regard to $(k,l)$-colourings. For proper circular arc graphs, we provide a method for $(k,l)$-colouring if $l \geq 1$, and establish an algebraic characterization for all maximally $(k,0)$-colourable proper circular arc graphs.
Finally, we investigate the bichromatic number and cochromatic with respect to lexicographic products and show several nice bounds. / Graduate
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/3514 |
| Date | 29 August 2011 |
| Creators | Epple, Dennis D. A. |
| Contributors | Huang, Jing |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Available to the World Wide Web |
Page generated in 0.0024 seconds