共查询到20条相似文献,搜索用时 35 毫秒
1.
2.
3.
4.
Ademir Hujdurović 《Journal of Graph Theory》2020,95(4):543-564
A clique (resp, independent set) in a graph is strong if it intersects every maximal independent set (resp, every maximal clique). A graph is clique intersect stable set (CIS) if all of its maximal cliques are strong and localizable if it admits a partition of its vertex set into strong cliques. In this paper we prove that a clique in a vertex-transitive graph is strong if and only if for every maximal independent set of . On the basis of this result we prove that a vertex-transitive graph is CIS if and only if it admits a strong clique and a strong independent set. We classify all vertex-transitive graphs of valency at most 4 admitting a strong clique, and give a partial characterization of 5-valent vertex-transitive graphs admitting a strong clique. Our results imply that every vertex-transitive graph of valency at most 5 that admits a strong clique is localizable. We answer an open question by providing an example of a vertex-transitive CIS graph which is not localizable. 相似文献
5.
Peyman Afshani Mahsa Ghandehari Mahya Ghandehari Hamed Hatami Ruzbeh Tusserkani Xuding Zhu 《Journal of Graph Theory》2005,49(4):325-335
This paper proves that if G is a graph (parallel edges allowed) of maximum degree 3, then χ′c(G) ≤ 11/3 provided that G does not contain H1 or H2 as a subgraph, where H1 and H2 are obtained by subdividing one edge of K (the graph with three parallel edges between two vertices) and K4, respectively. As χ′c(H1) = χ′c(H2) = 4, our result implies that there is no graph G with 11/3 < χ′c(G) < 4. It also implies that if G is a 2‐edge connected cubic graph, then χ′c(G) ≤ 11/3. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 325–335, 2005 相似文献
6.
The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are incident. Let □ , where □ denotes Cartesian product and H is an ‐regular graph of odd order, with (thus, G is s‐regular). We prove that , where is the minimum, over all bases of the cycle space of H, of the maximum length of a cycle in the basis. When and m is large, the lower bound is sharp. In particular, if , then □ , independent of m. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 7–18, 2008 相似文献
7.
We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001 相似文献
8.
强色指数的一个新的上界 总被引:1,自引:0,他引:1
给出了图的强色指数的一个新的上界,并指出几类恰好达到该上界的图,从而改进了Erodoes和Nesetri的强色指数猜想,在某种意义上证明了这个猜想。 相似文献
9.
10.
The strong chromatic index of a class of graphs 总被引:1,自引:0,他引:1
Jianzhuan Wu 《Discrete Mathematics》2008,308(24):6254-6261
The strong chromatic index of a graph G is the minimum integer k such that the edge set of G can be partitioned into k induced matchings. Faudree et al. [R.J. Faudree, R.H. Schelp, A. Gyárfás, Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211] proposed an open problem: If G is bipartite and if for each edge xy∈E(G), d(x)+d(y)≤5, then sχ′(G)≤6. Let H0 be the graph obtained from a 5-cycle by adding a new vertex and joining it to two nonadjacent vertices of the 5-cycle. In this paper, we show that if G (not necessarily bipartite) is not isomorphic to H0 and d(x)+d(y)≤5 for any edge xy of G then sχ′(G)≤6. The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs. 相似文献
11.
Golumbic, Hirst, and Lewenstein define a matching in a simple, finite, and undirected graph to be uniquely restricted if no other matching covers exactly the same set of vertices. We consider uniquely restricted edge-colorings of , defined as partitions of its edge set into uniquely restricted matchings, and study the uniquely restricted chromatic index of , defined as the minimum number of uniquely restricted matchings required for such a partition. For every graph , where is the classical chromatic index, the acyclic chromatic index, and the strong chromatic index of . While Vizing's famous theorem states that is either the maximum degree of or , two famous open conjectures due to Alon, Sudakov, and Zaks, and to Erdős and Nešetřil concern upper bounds on and in terms of . Since is sandwiched between these two parameters, studying upper bounds in terms of is a natural problem. We show that with equality if and only if some component of is . If is connected, bipartite, and distinct from , and is at least , then, adapting Lovász's elegant proof of Brooks’ theorem, we show that . Our proofs are constructive and yield efficient algorithms to determine the corresponding edge-colorings. 相似文献
12.
Suppose D is a subset of all positive integers. The distance graph G(Z, D) with distance set D is the graph with vertex set Z, and two vertices x and y are adjacent if and only if |x − y| ≡ D. This paper studies the chromatic number χ(Z, D) of G(Z, D). In particular, we prove that χ(Z, D) ≤ |D| + 1 when |D| is finite. Exact values of χ(G, D) are also determined for some D with |D| = 3. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 287–294, 1997 相似文献
13.
We show that there exist linear-time algorithms that compute the strong chromatic index and a maximum induced matching of tree-cographs when the decomposition tree is a part of the input. We also show that there exist efficient algorithms for the strong chromatic index of (bipartite) permutation graphs and of chordal bipartite graphs. 相似文献
14.
Some graphs admit drawings in the Euclidean plane (k-space) in such a (natural) way, that edges are represented as line segments of unit length. We say that they have the unit distance property.The influence of graph operations on the unit distance property is discussed. It is proved that the Cartesian product preserves the unit distance property in the Euclidean plane, while graph union, join, tensor product, strong product, lexicographic product and corona do not. It is proved that the Cartesian product preserves the unit distance property also in higher dimensions. 相似文献
15.
16.
We show that coloring the edges of a multigraph G in a particular order often leads to improved upper bounds for the chromatic index χ′(G). Applying this to simple graphs, we significantly generalize recent conditions based on the core of G 〈i.e., the subgraph of G induced by the vertices of degree Δ(G)〉, which insure that χ′(G) = Δ(G). Finally, we show that in any multigraph G in which every cycle of length larger than 2 contains a simple edge, where μ(G) is the largest edge multiplicity in G. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 311–326, 1999 相似文献
17.
Jakub Przybyło 《Discrete Mathematics》2017,340(10):2402-2407
Consider a positive integer and a graph with maximum degree and without isolated edges. The least so that a proper edge colouring exists such that for every pair of distinct vertices at distance at most in is denoted by . For , it has been proved that . For any in turn an infinite family of graphs is known with . We prove that, on the other hand, for . In particular, we show that if . 相似文献
18.
Given positive integers m, k, and s with m > ks, let Dm,k,s represent the set {1, 2, …, m} − {k, 2k, …, sk}. The distance graph G(Z, Dm,k,s) has as vertex set all integers Z and edges connecting i and j whenever |i − j| ∈ Dm,k,s. The chromatic number and the fractional chromatic number of G(Z, Dm,k,s) are denoted by χ(Z, Dm,k,s) and χf(Z, Dm,k,s), respectively. For s = 1, χ(Z, Dm,k,1) was studied by Eggleton, Erdős, and Skilton [6], Kemnitz and Kolberg [12], and Liu [13], and was solved lately by Chang, Liu, and Zhu [2] who also determined χf(Z, Dm,k,1) for any m and k. This article extends the study of χ(Z, Dm,k,s) and χf(Z, Dm,k,s) to general values of s. We prove χf(Z, Dm,k,s) = χ(Z, Dm,k,s) = k if m < (s + 1)k; and χf(Z, Dm,k,s) = (m + sk + 1)/(s + 1) otherwise. The latter result provides a good lower bound for χ(Z, Dm,k,s). A general upper bound for χ(Z, Dm,k,s) is obtained. We prove the upper bound can be improved to ⌈(m + sk + 1)/(s + 1)⌉ + 1 for some values of m, k, and s. In particular, when s + 1 is prime, χ(Z, Dm,k,s) is either ⌈(m + sk + 1)/(s + 1)⌉ or ⌈(m + sk + 1)/(s + 1)⌉ + 1. By using a special coloring method called the precoloring method, many distance graphs G(Z, Dm,k,s) are classified into these two possible values of χ(Z, Dm,k,s). Moreover, complete solutions of χ(Z, Dm,k,s) for several families are determined including the case s = 1 (solved in [2]), the case s = 2, the case (k, s + 1) = 1, and the case that k is a power of a prime. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 245–259, 1999 相似文献
19.
In this paper, we prove several new results on chromatic index critical graphs. We also prove that if G is a Δ(≥4)-critical graph, then
20.
Fractional chromatic number and circular chromatic number for distance graphs with large clique size
An Erratum has been published for this article in Journal of Graph Theory 48: 329–330, 2005 . Let M be a set of positive integers. The distance graph generated by M, denoted by G(Z, M), has the set Z of all integers as the vertex set, and edges ij whenever |i?j| ∈ M. We investigate the fractional chromatic number and the circular chromatic number for distance graphs, and discuss their close connections with some number theory problems. In particular, we determine the fractional chromatic number and the circular chromatic number for all distance graphs G(Z, M) with clique size at least |M|, except for one case of such graphs. For the exceptional case, a lower bound for the fractional chromatic number and an upper bound for the circular chromatic number are presented; these bounds are sharp enough to determine the chromatic number for such graphs. Our results confirm a conjecture of Rabinowitz and Proulx 22 on the density of integral sets with missing differences, and generalize some known results on the circular chromatic number of distance graphs and the parameter involved in the Wills' conjecture 26 (also known as the “lonely runner conjecture” 1 ). © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 129–146, 2004 相似文献