Acyclic edge colouring: Bounds and algorithms (Record no. 48806)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 02230nam a2200253Ia 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 160627s2008||||xx |||||||||||||| ||und|| |
| 080 ## - UNIVERSAL DECIMAL CLASSIFICATION NUMBER | |
| Universal Decimal Classification number | HBNI Th-3 |
| 100 ## - MAIN ENTRY--AUTHOR NAME | |
| Personal name | Rahul Muthu |
| Relator term | author |
| 245 ## - TITLE STATEMENT | |
| Title | Acyclic edge colouring: Bounds and algorithms |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Year of publication | 2008 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Number of Pages | x; 72p. |
| 502 ## - DISSERTATION NOTE | |
| Dissertation note | 2008 |
| 502 ## - DISSERTATION NOTE | |
| Degree Type | Ph.D |
| 502 ## - DISSERTATION NOTE | |
| Name of granting institution | HBNI |
| 520 3# - SUMMARY, ETC. | |
| Summary, etc | An acyclic edge colouring of a graph is an assignment of colours to its edges in such a way that incident edges get distinct colours, and the edges of any cycle use atleast three distinct colours. The latter condition is equivalent to the requirement that the subgraph induced by any pair of colour classes (set of edges receiving the same colour) is a forest. The minimum number of colours sufficient to acyclically colour the edges of a graph G, is called its acyclic chromatic index. This thesis studies the notion 'the acyclic edge colouring of graphs', in the context of two different aims, i) to get tight estimates on the minimum number of colours sufficient to achieve such colourings for any graph; ii) to actually produce such colourings using as few colours as possible. The acyclic colouring problem can be viewed from a combinatorial perspective and also from an algorithmic perspective. No good estimates on (Alpha)'(G) have been obtained for even highly structured classes like the complete graphs, or restricted families like bipartite graphs. From the algorithmic point of view it is NP-Hard to determine Alpha'(G) in general and even when restricted to subcubic, 2-degenerate graphs. Its close relationship to standard vertex colourings indicates that it could be useful in modelling and solving problems involving conflict free scheduling of activities. The acyclic edge colouring problem is also closely related to star and oriented colourings of line graphs which have applications in protocols for mobile communication. |
| 650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical Term | Computer Science |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Algorithm |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Combinatorics |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Graph Colouring |
| 720 1# - ADDED ENTRY--UNCONTROLLED NAME | |
| Thesis Advisor | Subramanian, C. R. |
| Relator term | Thesis advisor [ths] |
| 856 ## - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | http://www.imsc.res.in/xmlui/handle/123456789/116 |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Koha item type | THESIS & DISSERTATION |
| Withdrawn status | Lost status | Damaged status | Not for loan | Current library | Full call number | Accession Number | Uniform Resource Identifier | Koha item type |
|---|---|---|---|---|---|---|---|---|
| IMSc Library | HBNI Th-3 | 61042 | http://www.imsc.res.in/xmlui/handle/123456789/116 | THESIS & DISSERTATION |