Colouring graph when the number of colours is almost the maximum degree
Issue Date:
6-Jul-2001
Publisher:
ACM
Citation:
Molloy,M., Reed, B. Colouring Graphs whose Chromatic Number Is Almost Their Maximum Degree, Proceedings of the Third Latin American Symposium Theory of computing
Abstract (summary):
We consider for graphs of maximum degree , the problem
of determining whether (G) > k for various values of k.
We obtain sharp theorems characterizing when the barrier
to k colourability must be a local condition, i.e. a small
subgraph, and when it can be global. We also show that
for large xed , this problem is either NP-complete or can
be solved in linear time, and we determine precisely which
values of k correspond to each case
Description:
Conference Proceeding of STOC 2001.
Sponsorship:
SIGACT
Permanent Link:
https://hdl.handle.net/1807/9469
ISBN:
1-58113-349-9
Content Type:
Presentation
Items in TSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
link to htmlmap