Kneser图的分数染色临界性

图 G的一个分数染色是从 G的独立集的集合 ζ到区间 [0 ,1]的一个映射 C,使得对任意顶点x ,都有 :∑S∈ζ,s.t.x∈ sC(S) 1,我们将此分数染色的值定义为 ∑S∈ζc(S) .图 G的分数色数χf(G)是它的所有分数染色的值的下确界 .给出了分数染色临界性的定义并讨论了 Kneser图的分数染色临界性 .

关于Kneser图的一个分数染色性质

基于分数图论中a∶b染色定义,讨论了Kneser图的分数点染色数的性质,给出了一个计算Kneser图的分数点染色数的公式,并由此证明Stahl的一个关于Kneser图的分数染色数的猜想是不成立的.

Kneser图KG(11,5)平方图的色数(英文)

Kneser图KG(n,k)的顶点集包括一个n元集的所有k元子集,其中的任意两个顶点相邻当且仅当它们对应的子集不相交.一个图G的平方图G2的顶点集与G的顶点集相同,在G2中两个顶点之间有边当且仅当它们在G中的距离不超过2.通过理论分析和计算机搜索,得到8≤χ(KG2(11,5))≤10,10≤χ(KG2(13,6))≤16,其中前一个结论改进了已知的下界7和上界12.

两类广义Kneser图及其在考生面试问题中的应用

高校自主招生是高考改革中的一项新举措,它允许各高校对考生进行专家面试,决定录取与否.在考生数确定后,为保证面试工作的公平性,通过研究两类广义Kneser图的性质,对需要聘请的面试老师数建立了图论模型,并求得了满意的近似解,还提出了一个与Erds-Ko-Rado定理有关的猜想.

关于几类图的L(2,1)标号问题(英文)

图G的L( 2 ,1 )标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1 ,则｜f(x) -f(y) ｜≥ 2 ;若d(x ,y) =2 ,则｜f(x) -f(y) ｜≥ 1 .图G的L( 2 ,1 ) 标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) ≤Δ2 .本文给出了Kneser图 ,Mycieklski图 ,Descartes图 ,Halin图的λ值的上界 。

关于几类图的L(3,2,1)-标号问题

图G的L(2 ,1 )_标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1 ,则|f(x) -f(y) |≥ 2 ;若d(x ,y) =2 ,则 |f(x) -f(y) |≥ 1 .图G的L(2 ,1 )_标号数λ(G)是使得G有max{f(v) :v∈V(G) } =k的L(2 ,1 )_标号中的最小数k.该文将L(2 ,1 )_标号问题推广到更一般的情形即L(3,2 ,1 )_标号问题 ,并得出了Kneser图、高度不正则图、Halin图的λ3(G)