排序方式: 共有6条查询结果,搜索用时 46 毫秒
1
1.
Let be the complement of the intersection graph G of a family of translations of a compact convex figure in Rn. When n=2, we show that , where γ(G) is the size of the minimum dominating set of G. The bound on is sharp. For higher dimension we show that , for n?3. We also study the chromatic number of the complement of the intersection graph of homothetic copies of a fixed convex body in Rn. 相似文献
2.
Let F be a family of translates of a fixed convex set M in Rn. Let τ(F) and ν(F) denote the transversal number and the independence number of F, respectively. We show that ν(F)?τ(F)?8ν(F)-5 for n=2 and τ(F)?2n-1nnν(F) for n?3. Furthermore, if M is centrally symmetric convex body in the plane, then ν(F)?τ(F)?6ν(F)-3. 相似文献
3.
K. Nakprasit 《Discrete Mathematics》2008,308(16):3726-3728
The strong chromatic index s′(G) is the minimum integer t such that there is an edge-coloring of G with t colors in which every color class is an induced matching. Brualdi and Quinn conjecture that for every bipartite graph G, s′(G) is bounded by Δ1Δ2, where Δ1 and Δ2 are the maximum degrees among vertices in the two partite sets. We give the affirmative answer for Δ1=2. 相似文献
4.
5.
A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define for and We say that is -colorable if has a 2-coloring such that is an empty set or the induced subgraph has the maximum degree at most for and Let be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether is -colorable is NP-complete for every positive integer Moreover, we construct non--colorable planar graphs without 4-cycles and 5-cycles for every positive integer In contrast, we prove that is -colorable where and 相似文献
6.
The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n-element set, with two vertices adjacent if the sets are disjoint. The chromatic number of the Kneser graph K(n, k) is n–2k+2. Zoltán Füredi raised the question of determining the chromatic number of the square of the Kneser graph, where the square of a graph is the graph obtained by adding edges joining vertices at distance at most 2. We prove that (K2(2k+1, k))4k when k is odd and (K2(2k+1, k))4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on (K2(2k+1, k)), and we find the exact maximum size of an intersecting family of 4-sets in a 9-element set such that no two members of the family share three elements.This work was partially supported by NSF grant DMS-0099608Final version received: April 23, 2003 相似文献
1