首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Let α(H) be the stability number of a hypergraph H = (X, E). T(n, k, α) is the smallest q such that there exists a k-uniform hypergraph H with n vertices, q edges and with α(H) ? α. A k-uniform hypergraph H, with n vertices, T(n, k, α) edges and α(H) ?α is a Turan hypergraph. The value of T(n, 2, α) is given by a theorem of Turan. In this paper new lower bounds to T(n, k, α) are obtained and it is proved that an infinity of affine spaces are Turan hypergraphs.  相似文献   

2.
In this paper, we obtain linear time algorithms to determine the acyclic chromatic number, the star chromatic number, the non repetitive chromatic number and the clique chromatic number of P 4-tidy graphs and (q, q ? 4)-graphs, for every fixed q, which are the graphs such that every set with at most q vertices induces at most q ? 4 distinct P 4’s. These classes include cographs and P 4-sparse graphs. We also obtain a linear time algorithm to compute the harmonious chromatic number of connected P 4-tidy graphs and connected (q, q ? 4)-graphs. All these coloring problems are known to be NP-hard for general graphs. These algorithms are fixed parameter tractable on the parameter q(G), which is the minimum q such that G is a (q, q ? 4)-graph. We also prove that every connected (q, q ? 4)-graph with at least q vertices is 2-clique-colorable and that every acyclic coloring of a cograph is also nonrepetitive, generalizing the main result of Lyons (2011).  相似文献   

3.
For a positive integer k, a k-packing in a graph G is a subset A of vertices such that the distance between any two distinct vertices from A is more than k. The packing chromatic number of G is the smallest integer m such that the vertex set of G can be partitioned as V1,V2,…,Vm where Vi is an i-packing for each i. It is proved that the planar triangular lattice T and the three-dimensional integer lattice Z3 do not have finite packing chromatic numbers.  相似文献   

4.
In 1973, P. Erdös conjectured that for eachkε2, there exists a constantc k so that ifG is a graph onn vertices andG has no odd cycle with length less thanc k n 1/k , then the chromatic number ofG is at mostk+1. Constructions due to Lovász and Schriver show thatc k , if it exists, must be at least 1. In this paper we settle Erdös’ conjecture in the affirmative. We actually prove a stronger result which provides an upper bound on the chromatic number of a graph in which we have a bound on the chromatic number of subgraphs with small diameter.  相似文献   

5.
In this paper, we consider the following problem: of all tricyclic graphs or trees of order n with k pendant vertices (n,k fixed), which achieves the maximal signless Laplacian spectral radius?We determine the graph with the largest signless Laplacian spectral radius among all tricyclic graphs with n vertices and k pendant vertices. Then we show that the maximal signless Laplacian spectral radius among all trees of order n with k pendant vertices is obtained uniquely at Tn,k, where Tn,k is a tree obtained from a star K1,k and k paths of almost equal lengths by joining each pendant vertex to one end-vertex of one path. We also discuss the signless Laplacian spectral radius of Tn,k and give some results.  相似文献   

6.
The total chromatic number χT(G) of a graph G is the minimum number of colors needed to color the elements (vertices and edges) of G such that no adjacent or incident pair of elements receive the same color. G is called Type 1 if χT(G)=Δ(G)+1. In this paper we prove that the join of a complete inequibipartite graph Kn1,n2 and a path Pm is of Type 1.  相似文献   

7.
Denote by Tn,q the set of trees with n vertices and matching number q. Guo [On the Laplacian spectral radius of a tree, Linear Algebra Appl. 368 (2003) 379-385] gave the tree in Tn,q with the greatest value of the largest Laplacian eigenvalue. In this paper, we give another proof of this result. Using our method, we can go further beyond Guo by giving the tree in Tn,q with the second largest value of the largest Laplacian eigenvalue.  相似文献   

8.
Edge-colorings of multigraphs are studied where a generalization of Ramsey numbers is given. Let ${M_n^{(r)}}$ be the multigraph of order n, in which there are r edges between any two different vertices. Suppose q 1, q 2, . . . , q k and r are positive integers, and q i ≥ 2(1 ≤ i ≤ k), k > r. Let the multigraph Ramsey number ${f^{(r)} (q_1 ,q_2 , \ldots ,q_k )}$ be the minimum positive integer n such that in any k-edge coloring of ${M_n^{(r)}}$ (every edge is colored with one among k given colors, and edges between the same pair of vertices are colored with different colors), there must be ${i \in \{1,2,\ldots,k\}}$ such that ${M_n^{(r)}}$ has such a complete subgraph of order q i , of which all the edges are in color i. By Ramsey’s theorem it is easy to show ${f^{(r)} (q_1 ,q_2 , \ldots ,q_k )}$ exists for given q 1 ,q 2, . . . , q k and r. Lower and upper bounds for some multigraph Ramsey numbers are given.  相似文献   

9.
A graphG is called to be a 2-degree integral subgraph of aq-tree if it is obtained by deleting an edge e from an integral subgraph that is contained in exactlyq- 1 triangles. An added-vertexq-treeG with n vertices is obtained by taking two verticesu, v (u, v are not adjacent) in a q-treesT withn -1 vertices such that their intersection of neighborhoods ofu, v forms a complete graphK q , and adding a new vertexx, new edgesxu, xv, xv 1,xv 2, …,xv q- 4, where {v 1,v 2,...,v q?4} ?-K q . In this paper we prove that a graphG with minimum degree not equal toq -3 and chromatic polynomialP(G;λ) = λ(λ - 1) … (λ -q +2)(λ -q +1)3(λ -q) n- q- 2 withn ≥ q + 2 has and only has 2-degree integral subgraph of q-tree withn vertices and added-vertex q-tree withn vertices.  相似文献   

10.
The upper chromatic number of a hypergraph H=(X,E) is the maximum number k for which there exists a partition of X into non-empty subsets X=X1X2∪?∪Xk such that for each edge at least two vertices lie in one of the partite sets. We prove that for every n?3 there exists a 3-uniform hypergraph with n vertices, upper chromatic number 2 and ⌈n(n-2)/3⌉ edges which implies that a corresponding bound proved in [K. Diao, P. Zhao, H. Zhou, About the upper chromatic number of a co-hypergraph, Discrete Math. 220 (2000) 67-73] is best-possible.  相似文献   

11.
The equitable total chromatic number Χet (G) of a graphG is the smallest integerk for whichG has a total k-coloring such that the number of vertices and edges in any two color classes differ by at most one. In this paper, we determine the equitable total chromatic number of one class of the graphs.  相似文献   

12.
We give a concrete example of an infinite sequence of (pn,qn)-lens spaces L(pn,qn) with natural triangulations T(pn,qn) with pn tetrahedra such that L(pn,qn) contains a certain non-orientable closed surface which is fundamental with respect to T(pn,qn) and of minimal crosscap number among all closed non-orientable surfaces in L(pn,qn) and has n−2 parallel sheets of normal disks of a quadrilateral type disjoint from the pair of core circles of L(pn,qn). Actually, we can set p0=0, q0=1, pk+1=3pk+2qk and qk+1=pk+qk.  相似文献   

13.
The incidence chromatic number of G, denoted by χi(G), is the least number of colors such that G has an incidence coloring. In this paper, we determine the incidence chromatic number of the powers of paths, trees, which are min{n,2k+1}, and Δ(T2)+1, respectively. For the square of a Halin graph, we give an upper bound of its incidence chromatic number.  相似文献   

14.
Let f be a graph function which assigns to each graph H a non-negative integer f(H)≤|V(H)|. The f-game chromatic number of a graph G is defined through a two-person game. Let X be a set of colours. Two players, Alice and Bob, take turns colouring the vertices of G with colours from X. A partial colouring c of G is legal (with respect to graph function f) if for any subgraph H of G, the sum of the number of colours used in H and the number of uncoloured vertices of H is at least f(H). Both Alice and Bob must colour legally (i.e., the partial colouring produced needs to be legal). The game ends if either all the vertices are coloured or there are uncoloured vertices with no legal colour. In the former case, Alice wins the game. In the latter case, Bob wins the game. The f-game chromatic number of G, χg(f,G), is the least number of colours that the colour set X needs to contain so that Alice has a winning strategy. Let be the graph function defined as , for any n≥3 and otherwise. Then is called the acyclic game chromatic number of G. In this paper, we prove that any outerplanar graph G has acyclic game chromatic number at most 7. For any integer k, let ?k be the graph function defined as ?k(K2)=2 and ?k(Pk)=3 (Pk is the path on k vertices) and ?k(H)=0 otherwise. This paper proves that if k≥8 then for any tree T, χg(?k,T)≤9. On the other hand, if k≤6, then for any integer n, there is a tree T such that χg(?k,T)≥n.  相似文献   

15.
Let G be a connected graph of order 3 or more and let be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G, the color code of v is the k-tuple c(v)=(a1,a2,…,ak), where ai is the number of edges incident with v that are colored i (1?i?k). The coloring c is called detectable if distinct vertices have distinct color codes; while the detection number det(G) of G is the minimum positive integer k for which G has a detectable k-coloring. For each integer n?3, let DT(n) be the maximum detection number among all trees of order n and dT(n) the minimum detection number among all trees of order n. The numbers DT(n) and dT(n) are determined for all integers n?3. Furthermore, it is shown that for integers k?2 and n?3, there exists a tree T of order n having det(T)=k if and only if dT(n)?k?DT(n).  相似文献   

16.
Let c be a proper k-coloring of a connected graph G and Π=(C1,C2,…,Ck) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple cΠ(v):=(d(v,C1),d(v,C2),…,d(v,Ck)), where d(v,Ci)=min{d(v,x)|xCi},1≤ik. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χL(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χL(KG(n,2))=n−1 for all n≥5. Then, we prove that χL(KG(n,k))≤n−1, when nk2. Moreover, we present some bounds for the locating chromatic number of odd graphs.  相似文献   

17.
The total chromatic number χT(G) is the least number of colours needed to colour the vertices and edges of a graph G such that no incident or adjacent elements (vertices or edges) receive the same colour. The Total Colouring Conjecture (TCC) states that for every simple graph G, χT(G)?Δ(G)+2. This work verifies the TCC for powers of cycles even and 2<k<n/2, showing that there exists and can be polynomially constructed a (Δ(G)+2)-total colouring for these graphs.  相似文献   

18.
A deBruijn sequence of orderk, or a k-deBruijn sequence, over an alphabet A is a sequence of length |A|k in which the last element is considered adjacent to the first and every possible k-tuple from A appears exactly once as a string of k-consecutive elements in the sequence. We will say that a cyclic sequence is deBruijn-like if for some k, each of the consecutive k-element substrings is distinct.A vertex coloring χ:V(G)→[k] of a graph G is said to be proper if no pair of adjacent vertices in G receive the same color. Let C(v;χ) denote the multiset of colors assigned by a coloring χ to the neighbors of vertex v. A proper coloring χ of G is irregular if χ(u)=χ(v) implies that C(u;χ)≠C(v;χ). The minimum number of colors needed to irregularly color G is called the irregular chromatic number of G. The notion of the irregular chromatic number pairs nicely with other parameters aimed at distinguishing the vertices of a graph. In this paper, we demonstrate a connection between the irregular chromatic number of cycles and the existence of certain deBruijn-like sequences. We then determine the exact irregular chromatic number of Cn and Pn for n≥3, thus verifying two conjectures given by Okamoto, Radcliffe and Zhang.  相似文献   

19.
The chromatic capacityχcap(G) of a graph G is the largest k for which there exists a k-coloring of the edges of G such that, for every coloring of the vertices of G with the same colors, some edge is colored the same as both its vertices. We prove that there is an unbounded function f:NN such that χcap(G)?f(χ(G)) for almost every graph G, where χ denotes the chromatic number. We show that for any positive integers n and k with k?n/2 there exists a graph G with χ(G)=n and χcap(G)=n-k, extending a result of Greene. We obtain bounds on that are tight as r→∞, where is the complete n-partite graph with r vertices in each part. Finally, for any positive integers p and q we construct a graph G with χcap(G)+1=χ(G)=p that contains no odd cycles of length less than q.  相似文献   

20.
Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at the end of the game all the vertices of G are colored. The game chromatic number χg(G) is the minimum k for which the first player has a winning strategy. In this study, we analyze the asymptotic behavior of this parameter for a random graph Gn,p. We show that with high probability, the game chromatic number of Gn,p is at least twice its chromatic number but, up to a multiplicative constant, has the same order of magnitude. We also study the game chromatic number of random bipartite graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号