共查询到20条相似文献,搜索用时 46 毫秒
1.
We investigate the local chromatic number of shift graphs and prove that it is close to their chromatic number. This implies that the gap between the directed local chromatic number of an oriented graph and the local chromatic number of the underlying undirected graph can be arbitrarily large. We also investigate the minimum possible directed local chromatic number of oriented versions of “topologically t‐chromatic” graphs. We show that this minimum for large enough t‐chromatic Schrijver graphs and t‐chromatic generalized Mycielski graphs of appropriate parameters is ?t/4?+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 65‐82, 2010 相似文献
2.
Ko-Wei Lih 《Discrete Mathematics》2008,308(20):4653-4659
A graph is said to be a cover graph if it is the underlying graph of the Hasse diagram of a finite partially ordered set. We prove that the generalized Mycielski graphs Mm(C2t+1) of an odd cycle, Kneser graphs KG(n,k), and Schrijver graphs SG(n,k) are not cover graphs when m?0,t?1, k?1, and n?2k+2. These results have consequences in circular chromatic number. 相似文献
3.
We prove that coloring a 3-uniform 2-colorable hypergraph with c colors is NP-hard for any constant c. The best known algorithm [20] colors such a graph using O(n1/5) colors. Our result immediately implies that for any constants k ≥ 3 and c2 > c1 > 1, coloring a k-uniform c1-colorable hypergraph with c2 colors is NP-hard; the case k = 2, however, remains wide open.
This is the first hardness result for approximately-coloring a 3-uniform hypergraph that is colorable with a constant number
of colors. For k ≥ 4 such a result has been shown by [14], who also discussed the inherent difference between the k = 3 case and k ≥ 4.
Our proof presents a new connection between the Long-Code and the Kneser graph, and relies on the high chromatic numbers of
the Kneser graph [19,22] and the Schrijver graph [26]. We prove a certain maximization variant of the Kneser conjecture, namely
that any coloring of the Kneser graph by fewer colors than its chromatic number, has ‘many’ non-monochromatic edges.
* Research supported by NSF grant CCR-9987845.
† Supported by an Alon Fellowship and by NSF grant CCR-9987845.
‡ Work supported in part by NSF grants CCF-9988526 and DMS 9729992, and the State of New Jersery. 相似文献
4.
A new version of the Ruffini–Horner rule is presented for the evaluation of a polynomial of degree n at a point. In the PRAM model of parallel computation the new algorithm requires log n parallel steps with n/2+1 processors and the total number of arithmetic operations is n+⌈log2(n+1)⌉ -1 multiplications and n additions. If the polynomial is sparse, i.e., the number of nonzero coefficients is k≪ n, then the total number of operations is at most k(⌈log n⌉- ⌊log k⌋)+2k+⌈log n⌉. Moreover, similarly to the customary Ruffini–Horner rule, the algorithm is backward numerically stable. In other words,
the value provided by applying the algorithm in floating point arithmetic with machine precision μ coincides with the value
taken on at the same point by a slightly perturbed polynomial.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
5.
LiuYan YuanJinjiang WangShiying 《高校应用数学学报(英文版)》2000,15(1):1-6
Abstract. A simple graph G is induced matching extendable,shortly IM-extendable,if every in-duced matching of G is included in a perfect matching of G. The degree conditions of IM-extend-able graphs are researched in this paper. The main results are as follows: 相似文献
6.
The Linear 2-Arboricity of Planar Graphs 总被引:2,自引:0,他引:2
Let G be a planar graph with maximum degree Δ and girth g. The linear 2-arboricity la
2(G) of G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose component trees are paths of length at most 2. We prove that (1) la
2(G)≤⌈(Δ+1)/2⌉+12; (2) la
2(G)≤⌈(Δ+1)/2⌉+6 if g≥4; (3) la
2(G)≤⌈(Δ+1)/2⌉+2 if g≥5; (4) la
2(G)≤⌈(Δ+1)/2⌉+1 if g≥7.
Received: June 28, 2001 Final version received: May 17, 2002
Acknowledgments. This work was done while the second and third authors were visiting the Institute of Mathematics, Academia Sinica, Taipei.
The financial support provided by the Institute is greatly appreciated. 相似文献
7.
A properk-coloring of a graph is acyclic if every 2-chromatic subgraph is acyclic. Borodin showed that every planar graph has an acyclic
5-coloring. This paper shows that the acyclic chromatic number of the projective plane is at most 7. The acyclic chromatic
number of an arbitrary surface with Euler characteristic η=−γ is at mostO(γ4/7). This is nearly tight; for every γ>0 there are graphs embeddable on surfaces of Euler characteristic −γ whose acyclic chromatic
number is at least Ω(γ4/7/(logγ)1/7). Therefore, the conjecture of Borodin that the acyclic chromatic number of any surface but the plane is the same as its
chromatic number is false for all surfaces with large γ (and may very well be false for all surfaces).
This author's research was supported in part by a United States Israeli BSF grant.
This author's research was supported by the Ministry of Research and Technology of Slovenia, Research Project P1-0210-101-92.
This author's research was supported by the Office of Naval Research, grant number N00014-92-J-1965. 相似文献
8.
Combining Ky Fan’s theorem with ideas of Greene and Matoušek we prove a generalization of Dol’nikov’s theorem. Using another variant of the Borsuk–Ulam theorem due to Tucker and Bacon, we also prove the presence of all possible completely multicolored t-vertex complete bipartite graphs in t-colored t-chromatic Kneser graphs and in several of their relatives. In particular, this implies a generalization of a recent result of G. Spencer and F.E. Su. 相似文献
9.
In this paper we consider the familiar bin-packing problem and its associated set-partitioning formulation. We show that the
optimal solution to the bin-packing problem can be no larger than 4/3 ⌈Z
LP⌉, whereZ
LP is the optimal solution value of the linear programming relaxation of the set-partitioning formulation. An example is provided
to show that the bound is tight. A by-product of our analysis is a new worst-case bound on the performance of the well studied
First Fit Decreasing and Best Fit Decreasing heuristics.
This research was supported in part by ONR Contracts N00014-90-J-1649 and N00014-95-1-0232, and NSF Contracts DDM-8922712
and DDM-9322828. 相似文献
10.
For any two-colouring of the segments determined by 3n − 3 points in general position in the plane, either the first colour class contains a triangle, or there is a noncrossing
cycle of length n in the second colour class, and this result is tight. We also give a series of more general estimates on off-diagonal geometric
graph Ramsey numbers in the same spirit. Finally we investigate the existence of large noncrossing monochromatic matchings
in multicoloured geometric graphs.
Research partially supported by Hungarian Scientific Research Grants OTKA T043631 and NK67867. 相似文献
11.
Manouchehr Zaker 《Discrete Mathematics》2011,(14):1365
In this paper we discuss the existence of lower bounds for the chromatic number of graphs in terms of the average degree or the coloring number of graphs. We obtain a lower bound for the chromatic number of K1,t-free graphs in terms of the maximum degree and show that the bound is tight. For any tree T, we obtain a lower bound for the chromatic number of any K2,t-free and T-free graph in terms of its average degree. This answers affirmatively a modified version of Problem 4.3 in [T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley, New York, 1995]. More generally, we discuss δ-bounded families of graphs and then we obtain a necessary and sufficient condition for a family of graphs to be a δ-bounded family in terms of its induced bipartite Turán number. Our last bound is in terms of forbidden induced even cycles in graphs; it extends a result in [S.E. Markossian, G.S. Gasparian, B.A. Reed, β-perfect graphs, J. Combin. Theory Ser. B 67 (1996) 1–11]. 相似文献
12.
K. Matomäki 《Acta Mathematica Hungarica》2010,128(4):307-314
We construct prime-representing functions. In particular we show that there exist real numbers α > 1 such that ⌈α
2
n
⌉ is prime for all n ∈ ℕ. Indeed the set consisting of such numbers α has the cardinality of the continuum. 相似文献
13.
In this note, we investigate some properties of local Kneser graphs defined in [János Körner, Concetta Pilotto, Gábor Simonyi, Local chromatic number and sperner capacity, J. Combin. Theory Ser. B 95 (1) (2005) 101-117]. In this regard, as a generalization of the Erdös-Ko-Rado theorem, we characterize the maximum independent sets of local Kneser graphs. Next, we provide an upper bound for their chromatic number. 相似文献
14.
N. Alon 《Israel Journal of Mathematics》1988,62(3):311-325
Alinear forest is a forest in which each connected component is a path. Thelinear arboricity la(G) of a graphG is the minimum number of linear forests whose union is the set of all edges ofG. Thelinear arboricity conjecture asserts that for every simple graphG with maximum degree Δ=Δ(G),
. Although this conjecture received a considerable amount of attention, it has been proved only for Δ≦6, Δ=8 and Δ=10, and
the best known general upper bound for la(G) is la(G)≦⌈3Δ/5⌉ for even Δ and la(G)≦⌈(3Δ+2)/5⌉ for odd Δ. Here we prove that for everyɛ>0 there is a Δ0=Δ0(ɛ) so that la(G)≦(1/2+ɛ)Δ for everyG with maximum degree Δ≧Δ0. To do this, we first prove the conjecture for everyG with an even maximum degree Δ and withgirth g≧50Δ.
Research supported in part by Allon Fellowship, by a Bat Sheva de Rothschild grant, by the Fund for Basic Research administered
by the Israel Academy of Sciences and by a B.S.F. Bergmann Memorial grant. 相似文献
15.
We show that any point in the convex hull of each of (d+1) sets of (d+1) points in general position in ℝ
d
is contained in at least ⌈(d+1)2/2⌉ simplices with one vertex from each set. This improves the known lower bounds for all d≥4. 相似文献
16.
Katsuhiro Ota 《Graphs and Combinatorics》1988,4(1):333-354
An edge of a 3-connected graph is calledcontractible if its contraction results in a 3-connected graph. Ando, Enomoto and Saito proved that every 3-connected graph of order at least five has |G|/2 or more contractible edges. As another lower bound, we prove that every 3-connected graph, except for six graphs, has at least (2|E(G)| + 12)/7 contractible edges. We also determine the extremal graphs. Almost all of these extremal graphsG have more than |G|/2 contractible edges. 相似文献
17.
We introduce and discuss generalizations of the problem of independent transversals. Given a graph property
, we investigate whether any graph of maximum degree at most d with a vertex partition into classes of size at least p admits a transversal having property
. In this paper we study this problem for the following properties
: “acyclic”, “H-free”, and “having connected components of order at most r”.
We strengthen a result of [13]. We prove that if the vertex set of a d-regular graph is partitioned into classes of size d+⌞d/r⌟, then it is possible to select a transversal inducing vertex disjoint trees on at most r vertices. Our approach applies appropriate triangulations of the simplex and Sperner’s Lemma. We also establish some limitations
on the power of this topological method.
We give constructions of vertex-partitioned graphs admitting no independent transversals that partially settles an old question
of Bollobás, Erdős and Szemerédi. An extension of this construction provides vertex-partitioned graphs with small degree such
that every transversal contains a fixed graph H as a subgraph.
Finally, we pose several open questions.
* Research supported by the joint Berlin/Zurichgrad uate program Combinatorics, Geometry, Computation, financed by the German
Science Foundation (DFG) and ETH Zürich.
† Research partially supported by Hungarian National Research Fund grants T-037846, T-046234 and AT-048826. 相似文献
18.
Hadwiger's conjecture asserts that every graph with chromatic number t contains a complete minor of order t. Given integers , the Kneser graph is the graph with vertices the k‐subsets of an n‐set such that two vertices are adjacent if and only if the corresponding k‐subsets are disjoint. We prove that Hadwiger's conjecture is true for the complements of Kneser graphs. 相似文献
19.
It was conjectured in 1981 by the third author that if a graph G does not contain more than t pairwise edge-disjoint triangles, then there exists a set of at most 2t edges that shares an edge with each triangle of G. In this paper, we prove this conjecture for odd-wheel-free graphs and for ‘triangle-3-colorable’ graphs, where the latter
property means that the edges of the graph can be colored with three colors in such a way that each triangle receives three
distinct colors on its edges. Among the consequences we obtain that the conjecture holds for every graph with chromatic number
at most four. Also, two subclasses of K
4-free graphs are identified, in which the maximum number of pairwise edge-disjoint triangles is equal to the minimum number
of edges covering all triangles. In addition, we prove that the recognition problem of triangle-3-colorable graphs is intractable. 相似文献
20.
A graphG ischromatically k-connected if every vertex cutset induces a subgraph with chromatic number at leastk. This concept arose in some work, involving the third author, on Ramsey Theory. (For the reference, see the text.) Here we begin the study of chromatic connectivity for its own sake. We show thatG is chromaticallyk-connected iff every homomorphic image of it isk-connected. IfG has no triangles then it is at most chromatically 1-connected, but we prove that the Kneser graphs provide examples ofK
4-free graphs with arbitrarily large chromatic connectivity. We also verify thatK
4-free planar graphs are at most chromatically 2-connected.This work was supported by grants from NSERC of Canada. 相似文献