Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
On the maximum degree chromatic number of a graph
ENGLISH ABSTRACT: Determining the (classical) chromatic number of a graph (i.e. finding the smallest number of colours with which the vertices of a graph may be coloured so that no two adjacent vertices receive the same colour) is a well known combinatorial optimization problem and is widely enco...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2012
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613986037432320 |
|---|---|
| access_status_str | Open Access |
| author | Nieuwoudt, Isabelle |
| author2 | Van Vuuren, J. H. |
| author_browse | Nieuwoudt, Isabelle Van Vuuren, J. H. |
| author_facet | Van Vuuren, J. H. Nieuwoudt, Isabelle |
| author_sort | Nieuwoudt, Isabelle |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | ENGLISH ABSTRACT: Determining the (classical) chromatic number of a graph (i.e. finding the smallest number of colours with
which the vertices of a graph may be coloured so that no two adjacent vertices receive the same colour)
is a well known combinatorial optimization problem and is widely encountered in scheduling problems.
Since the late 1960s the notion of the chromatic number has been generalized in several ways by relaxing
the restriction of independence of the colour classes. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/46214 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:44:51.414Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2012 |
| publishDateRange | 2012 |
| publishDateSort | 2012 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/46214 On the maximum degree chromatic number of a graph Nieuwoudt, Isabelle Van Vuuren, J. H. Grobler, P. J. P. Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Graph coloring Graphic methods Graphic methods Graph algorithms Dissertations -- Applied mathematics Theses -- Applied mathematics ENGLISH ABSTRACT: Determining the (classical) chromatic number of a graph (i.e. finding the smallest number of colours with which the vertices of a graph may be coloured so that no two adjacent vertices receive the same colour) is a well known combinatorial optimization problem and is widely encountered in scheduling problems. Since the late 1960s the notion of the chromatic number has been generalized in several ways by relaxing the restriction of independence of the colour classes. AFRIKAANSE OPSOMMING: Die bepaling van die (klassieke) chromatiese getal van ’n grafiek (naamlik die kleinste aantal kleure waarmee die punte van ’n grafiek gekleur kan word sodat geen twee naasliggende punte dieselfde kleur ontvang nie) is ’n bekende kombinatoriese optimeringsprobleem wat wyd in skeduleringstoepassings te¨egekom word. Sedert die laat 1960s is die definisie van die chromatiese getal op verskeie maniere veralgemeen deur die vereiste van onafhanklikheid van die kleurklasse te verslap. Thesis (DPhil)--Stellenbosch University, 2007. Doctoral 2012-08-11T00:27:19Z 2012-08-11T00:27:19Z 2007-12 Thesis http://hdl.handle.net/10019.1/46214 en_ZA Stellenbosch University 208 p. : ill. application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Graph coloring Graphic methods Graphic methods Graph algorithms Dissertations -- Applied mathematics Theses -- Applied mathematics Nieuwoudt, Isabelle On the maximum degree chromatic number of a graph |
| title | On the maximum degree chromatic number of a graph |
| title_full | On the maximum degree chromatic number of a graph |
| title_fullStr | On the maximum degree chromatic number of a graph |
| title_full_unstemmed | On the maximum degree chromatic number of a graph |
| title_short | On the maximum degree chromatic number of a graph |
| title_sort | on the maximum degree chromatic number of a graph |
| topic | Graph coloring Graphic methods Graphic methods Graph algorithms Dissertations -- Applied mathematics Theses -- Applied mathematics |
| url | http://hdl.handle.net/10019.1/46214 |
| work_keys_str_mv | AT nieuwoudtisabelle onthemaximumdegreechromaticnumberofagraph |