intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Báo cáo toán học: "On the functions with values in [α(G), χ(G)]"

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:5

67
lượt xem
4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Let G be a graph with vertex set V (G) = {1, . . . , n} and edge set E(G). We are interested in studying the functions of the graph G whose values belong to the interval [ (G), (G)]. Here (G) is the size of the largest stable set in G and (G) is the smallest number of cliques that cover the vertices of G. It is well known (see, for example, [1]) that for some  0 it is impossible to approximate in polynomial time (G) and (G) within a factor of n, assuming P 6= NP. We suppose that better approximation could...

Chủ đề:
Lưu

Nội dung Text: Báo cáo toán học: "On the functions with values in [α(G), χ(G)]"

ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2