共查询到20条相似文献,搜索用时 46 毫秒
1.
The packing chromatic number χρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into packings with pairwise different widths. Several lower and upper bounds are obtained for the packing chromatic number of Cartesian products of graphs. It is proved that the packing chromatic number of the infinite hexagonal lattice lies between 6 and 8. Optimal lower and upper bounds are proved for subdivision graphs. Trees are also considered and monotone colorings are introduced. 相似文献
2.
For graphs of bounded maximum degree, we consider acyclic t-improper colourings, that is, colourings in which each bipartite subgraph consisting of the edges between two colour classes is acyclic, and each colour class induces a graph with maximum degree at most t.We consider the supremum, over all graphs of maximum degree at most d, of the acyclic t-improper chromatic number and provide t-improper analogues of results by Alon, McDiarmid and Reed [N. Alon, C.J.H. McDiarmid, B. Reed, Acyclic coloring of graphs, Random Structures Algorithms 2 (3) (1991) 277-288] and Fertin, Raspaud and Reed [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs, J. Graph Theory 47 (3) (2004) 163-182]. 相似文献
3.
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. 相似文献
4.
Erd?s conjectured that if G is a triangle free graph of chromatic number at least k≥3, then it contains an odd cycle of length at least k 2?o(1) [13,15]. Nothing better than a linear bound ([3], Problem 5.1.55 in [16]) was so far known. We make progress on this conjecture by showing that G contains an odd cycle of length at least Ω(k log logk). Erd?s’ conjecture is known to hold for graphs with girth at least five. We show that if a graph with girth four is C 5 free, then Erd?s’ conjecture holds. When the number of vertices is not too large we can prove better bounds on χ. We also give bounds on the chromatic number of graphs with at most r cycles of length 1 mod k, or at most s cycles of length 2 mod k, or no cycles of length 3 mod k. Our techniques essentially consist of using a depth first search tree to decompose the graph into ordered paths, which are then fed to an online coloring algorithm. Using this technique we give simple proofs of some old results, and also obtain several other results. We also obtain a lower bound on the number of colors which an online coloring algorithm needs to use to color triangle free graphs. 相似文献
5.
Incidence coloring of a graph G is a mapping from the set of incidences to a color-set C such that adjacent incidences of G are assigned distinct colors. Since 1993, numerous fruitful results as regards incidence coloring have been proved. However, some of them are incorrect. We remedy the error of the proof in [R.A. Brualdi, J.J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51-58] concerning complete bipartite graphs. Also, we give an example to show that an outerplanar graph with Δ=4 is not 5-incidence colorable, which contradicts [S.D. Wang, D.L. Chen, S.C. Pang, The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Math. 256 (2002) 397-405], and prove that the incidence chromatic number of the outerplanar graph with Δ≥7 is Δ+1. Moreover, we prove that the incidence chromatic number of the cubic Halin graph is 5. Finally, to improve the lower bound of the incidence chromatic number, we give some sufficient conditions for graphs that cannot be (Δ+1)-incidence colorable. 相似文献
6.
A new coloring theorem of Kneser graphs 总被引:1,自引:0,他引:1
Peng-An Chen 《Journal of Combinatorial Theory, Series A》2011,118(3):1062-1071
In 1997, Johnson, Holroyd and Stahl conjectured that the circular chromatic number of the Kneser graphs KG(n,k) is equal to the chromatic number of these graphs. This was proved by Simonyi and Tardos (2006) [13] and independently by Meunier (2005) [10], if χ(KG(n,k)) is even. In this paper, we propose an alternative version of Kneser's coloring theorem to confirm the Johnson-Holroyd-Stahl conjecture. 相似文献
7.
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. 相似文献
8.
Carsten Schultz 《Journal of Combinatorial Theory, Series A》2011,118(8):2291-2318
The stable Kneser graph SGn,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K2,SGn,k)?Sk. The dihedral group D2m acts canonically on SGn,k, the group C2 with 2 elements acts on K2. We almost determine the (C2×D2m)-homotopy type of Hom(K2,SGn,k) and use this to prove the following results.The graphs SG2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SGn,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SGn,k,G) is (r−1)-connected and χ(G)<r+k+2. 相似文献
9.
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 相似文献
10.
A well-established generalization of graph coloring is the concept of list coloring. In this setting, each vertex v of a graph G is assigned a list L(v) of k colors and the goal is to find a proper coloring c of G with c(v)∈L(v). The smallest integer k for which such a coloring c exists for every choice of lists is called the list chromatic number of G and denoted by χl(G).We study list colorings of Cartesian products of graphs. We show that unlike in the case of ordinary colorings, the list chromatic number of the product of two graphs G and H is not bounded by the maximum of χl(G) and χl(H). On the other hand, we prove that χl(G×H)?min{χl(G)+col(H),col(G)+χl(H)}-1 and construct examples of graphs G and H for which our bound is tight. 相似文献
11.
For a graph G, a random n‐lift of G has the vertex set V(G)×[n] and for each edge [u, v] ∈ E(G), there is a random matching between {u}×[n] and {v}×[n]. We present bounds on the chromatic number and on the independence number of typical random lifts, with G fixed and n→∞. For the independence number, upper and lower bounds are obtained as solutions to certain optimization problems on the base graph. For a base graph G with chromatic number χ and fractional chromatic number χf, we show that the chromatic number of typical lifts is bounded from below by const ? and also by const ? χf/log2χf (trivially, it is bounded by χ from above). We have examples of graphs where the chromatic number of the lift equals χ almost surely, and others where it is a.s. O(χ/logχ). Many interesting problems remain open. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 1–22, 2002 相似文献
12.
Wensong Lin 《Discrete Mathematics》2008,308(16):3565-3573
The generalized Mycielskians of graphs (also known as cones over graphs) are the natural generalization of the Mycielskians of graphs (which were first introduced by Mycielski in 1955). Given a graph G and any integer p?0, one can transform G into a new graph μp(G), the p-Mycielskian of G. In this paper, we study the kth chromatic numbers χk of Mycielskians and generalized Mycielskians of graphs. We show that χk(G)+1?χk(μ(G))?χk(G)+k, where both upper and lower bounds are attainable. We then investigate the kth chromatic number of Mycielskians of cycles and determine the kth chromatic number of p-Mycielskian of a complete graph Kn for any integers k?1, p?0 and n?2. Finally, we prove that if a graph G is a/b-colorable then the p-Mycielskian of G, μp(G), is (at+bp+1)/bt-colorable, where . And thus obtain graphs G with m(G) grows exponentially with the order of G, where m(G) is the minimal denominator of a a/b-coloring of G with χf(G)=a/b. 相似文献
13.
《Discrete Mathematics》2023,346(1):113162
The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths. 相似文献
14.
Xuding Zhu 《Journal of Graph Theory》2008,59(4):261-278
This article proves the following result: Let G and G′ be graphs of orders n and n′, respectively. Let G* be obtained from G by adding to each vertex a set of n′ degree 1 neighbors. If G* has game coloring number m and G′ has acyclic chromatic number k, then the Cartesian product G□G′ has game chromatic number at most k(k + m ? 1). As a consequence, the Cartesian product of two forests has game chromatic number at most 10, and the Cartesian product of two planar graphs has game chromatic number at most 105. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 261–278, 2008 相似文献
15.
A k-colouring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given(hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3. 相似文献
16.
Akira Saito 《Discrete Mathematics》2009,309(16):5000-1723
We consider 2-factors with a bounded number of components in the n-times iterated line graph Ln(G). We first give a characterization of graph G such that Ln(G) has a 2-factor containing at most k components, based on the existence of a certain type of subgraph in G. This generalizes the main result of [L. Xiong, Z. Liu, Hamiltonian iterated line graphs, Discrete Math. 256 (2002) 407-422]. We use this result to show that the minimum number of components of 2-factors in the iterated line graphs Ln(G) is stable under the closure operation on a claw-free graph G. This extends results in [Z. Ryjá?ek, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217-224; Z. Ryjá?ek, A. Saito, R.H. Schelp, Closure, 2-factors and cycle coverings in claw-free graphs, J. Graph Theory 32 (1999) 109-117; L. Xiong, Z. Ryjá?ek, H.J. Broersma, On stability of the hamiltonian index under contractions and closures, J. Graph Theory 49 (2005) 104-115]. 相似文献
17.
Diego Scheide 《Discrete Mathematics》2009,309(15):4920-4925
Two of the basic results on edge coloring are Vizing’s Theorem [V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30 (in Russian); V.G. Vizing, The chromatic class of a multigraph, Kibernetika (Kiev) 3 (1965) 29-39 (in Russian). English translation in Cybernetics 1 32-41], which states that the chromatic index χ′(G) of a (multi)graph G with maximum degree Δ(G) and maximum multiplicity μ(G) satisfies Δ(G)≤χ′(G)≤Δ(G)+μ(G), and Holyer’s Theorem [I. Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 10 (1981) 718-720], which states that the problem of determining the chromatic index of even a simple graph is NP-hard. Hence, a good characterization of those graphs for which Vizing’s upper bound is attained seems to be unlikely. On the other hand, Vizing noticed in the first two above-cited references that the upper bound cannot be attained if Δ(G)=2μ(G)+1≥5. In this paper we discuss the problem: For which values Δ,μ does there exist a graph G satisfying Δ(G)=Δ, μ(G)=μ, and χ′(G)=Δ+μ. 相似文献
18.
Christine T. Cheng 《Discrete Mathematics》2009,309(16):5169-434
A vertex k-coloring of graph G is distinguishing if the only automorphism of G that preserves the colors is the identity map. It is proper-distinguishing if the coloring is both proper and distinguishing. The distinguishing number ofG, D(G), is the smallest integer k so that G has a distinguishing k-coloring; the distinguishing chromatic number ofG, χD(G), is defined similarly.It has been shown recently that the distinguishing number of a planar graph can be determined efficiently by counting a related parameter-the number of inequivalent distinguishing colorings of the graph. In this paper, we demonstrate that the same technique can be used to compute the distinguishing number and the distinguishing chromatic number of an interval graph. We make use of PQ-trees, a classic data structure that has been used to recognize and test the isomorphism of interval graphs; our algorithms run in O(n3log3n) time for graphs with n vertices. We also prove a number of results regarding the computational complexity of determining a graph’s distinguishing chromatic number. 相似文献
19.
We consider the localization game played on graphs, wherein a set of cops attempt to determine the exact location of an invisible robber by exploiting distance probes. The corresponding optimization parameter for a graph G is called the localization number and is written as ζ(G). We settle a conjecture of Bosek et al by providing an upper bound on the chromatic number as a function of the localization number. In particular, we show that every graph with ζ(G) ≤ k has degeneracy less than 3k and, consequently, satisfies χ(G) ≤ 3ζ(G). We show further that this degeneracy bound is tight. We also prove that the localization number is at most 2 in outerplanar graphs, and we determine, up to an additive constant, the localization number of hypercubes. 相似文献
20.
An edge-coloring is an association of colors to the edges of a graph, in such a way that no pair of adjacent edges receive the same color. A graph G is Class 1 if it is edge-colorable with a number of colors equal to its maximum degree Δ(G). To determine whether a graph G is Class 1 is NP-complete [I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718-720]. First, we propose edge-decompositions of a graph G with the goal of edge-coloring G with Δ(G) colors. Second, we apply these decompositions for identifying new subsets of Class 1 join graphs and cobipartite graphs. Third, the proposed technique is applied for proving that the chromatic index of a graph is equal to the chromatic index of its semi-core, the subgraph induced by the maximum degree vertices and their neighbors. Finally, we apply these decomposition tools to a classical result [A.J.W. Hilton, Z. Cheng, The chromatic index of a graph whose core has maximum degree 2, Discrete Math. 101 (1992) 135-147] that relates the chromatic index of a graph to its core, the subgraph induced by the maximum degree vertices. 相似文献