Loading…
Locally bounded hereditary subclasses of k-colourable graphs
A vertex colouring C 1, C 2,…, C k of a graph G is called l- bounded ( l⩾0) if | C i⧹N(u)|⩽l for all i=1,2,…, k and for every vertex u∈VG⧹ C i ; here N( u) is the neighbourhood of u. Let C( k, l) be the class of all graphs having an l-bounded k-colouring. We show that for all k and l the class C( k,...
Saved in:
| Published in: | Discrete Applied Mathematics 2001-10, Vol.114 (1), p.301-311 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | English |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | A vertex colouring
C
1,
C
2,…,
C
k
of a graph
G is called
l-
bounded (
l⩾0) if
|
C
i⧹N(u)|⩽l
for all
i=1,2,…,
k and for every vertex
u∈VG⧹
C
i
; here
N(
u) is the neighbourhood of
u. Let
C(
k,
l) be the class of all graphs having an
l-bounded
k-colouring. We show that for all
k and
l the class
C(
k,
l) can be described in terms of forbidden induced subgraphs. This result implies the existence of polynomial time algorithms recognizing
C(
k,
l). We also find the minimal set of forbidden induced subgraphs for the class
C(3,1). |
|---|---|
| ISSN: | 0166-218X 1872-6771 |
| DOI: | 10.1016/S0166-218X(00)00378-4 |