共查询到20条相似文献,搜索用时 15 毫秒
1.
The weak chromatic number, or clique chromatic number (CCHN) of a graph is the minimum number of colors in a vertex coloring, such that every maximal clique gets at least two colors. The weak chromatic index, or clique chromatic index (CCHI) of a graph is the CCHN of its line graph.Most of the results here are upper bounds for the CCHI, as functions of some other graph parameters, and contrasting with lower bounds in some cases. Algorithmic aspects are also discussed; the main result within this scope (and in the paper) shows that testing whether the CCHI of a graph equals is NP-complete. We deal with the CCHN of the graph itself as well. 相似文献
2.
3.
Bo-Jr Li 《Discrete Mathematics》2008,308(11):2075-2079
A clique in a graph G is a complete subgraph of G. A clique covering (partition) of G is a collection C of cliques such that each edge of G occurs in at least (exactly) one clique in C. The clique covering (partition) numbercc(G) (cp(G)) of G is the minimum size of a clique covering (partition) of G. This paper gives alternative proofs, using a unified approach, for the results on the clique covering (partition) numbers of line graphs obtained by McGuinness and Rees [On the number of distinct minimal clique partitions and clique covers of a line graph, Discrete Math. 83 (1990) 49-62]. We also employ the proof techniques to give an alternative proof for the De Brujin-Erd?s Theorem. 相似文献
4.
A graph G is collapsible if for every even subset X⊆V(G), G has a subgraph Γ such that G−E(Γ) is connected and the set of odd-degree vertices of Γ is X. A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77-87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347-364]. 相似文献
5.
Let D be a set of positive integers. The distance graph G(Z,D) with distance set D is the graph with vertex set Z in which two vertices x,y are adjacent if and only if |x−y|D. The fractional chromatic number, the chromatic number, and the circular chromatic number of G(Z,D) for various D have been extensively studied recently. In this paper, we investigate the fractional chromatic number, the chromatic number, and the circular chromatic number of the distance graphs with the distance sets of the form Dm,[k,k′]={1,2,…,m}−{k,k+1,…,k′}, where m, k, and k′ are natural numbers with m≥k′≥k. In particular, we completely determine the chromatic number of G(Z,Dm,[2,k′]) for arbitrary m, and k′. 相似文献
6.
Shuchao Li 《Discrete Mathematics》2009,309(14):4843-2218
By applying a discharging method, we give new lower bounds for the sizes of edge chromatic critical graphs for small maximum degrees. Furthermore, it is also proved that if G is a graph embeddable in a surface S with characteristic cS=−4 or −5 or −6, then G is class one if its maximum degree Δ≥10 or 11 or 12 respectively. 相似文献
7.
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 相似文献
8.
Mohammad Ghebleh 《Discrete Mathematics》2008,308(1):144-147
The line index of a graph G is the smallest k such that the kth iterated line graph of G is nonplanar. We show that the line index of a graph is either infinite or it is at most 4. Moreover, we give a full characterization of all graphs with respect to their line index. 相似文献
9.
10.
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 相似文献
11.
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. 相似文献
12.
It is proved here that any edge-coloring critical graph of order n and maximum degree Δ?8 has the size at least 3(n+Δ−8). It generalizes a result of Hugh Hind and Yue Zhao. 相似文献
13.
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 相似文献
14.
Thomassen [Reflections on graph theory, J. Graph Theory 10 (1986) 309-324] conjectured that every 4-connected line graph is hamiltonian. An hourglass is a graph isomorphic to K5-E(C4), where C4 is a cycle of length 4 in K5. In Broersma et al. [On factors of 4-connected claw-free graphs, J. Graph Theory 37 (2001) 125-136], it is shown that every 4-connected line graph without an induced subgraph isomorphic to the hourglass is hamiltonian connected. In this note, we prove that every 3-connected, essentially 4-connected hourglass free line graph, is hamiltonian connected. 相似文献
15.
《Discrete Mathematics》2022,345(11):113020
16.
The boxicity of a graph H, denoted by , is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in Rk. In this paper we show that for a line graph G of a multigraph, , where Δ(G) denotes the maximum degree of G. Since G is a line graph, Δ(G)≤2(χ(G)−1), where χ(G) denotes the chromatic number of G, and therefore, . For the d-dimensional hypercube Qd, we prove that . The question of finding a nontrivial lower bound for was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795–5800].The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once). 相似文献
17.
The concept of the star chromatic number of a graph was introduced by Vince (A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551–559), which is a natural generalization of the chromatic number of a graph. This paper calculates the star chromatic numbers of three infinite families of planar graphs. More precisely, the first family of planar graphs has star chromatic numbers consisting of two alternating infinite decreasing sequences between 3 and 4; the second family of planar graphs has star chromatic numbers forming an infinite decreasing sequence between 3 and 4; and the third family of planar graphs has star chromatic number 7/2. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 33–42, 1998 相似文献
18.
WANGWEIFAN ZHANGKEMIN 《高校应用数学学报(英文版)》1997,12(4):455-462
A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g. 相似文献
19.
20.
On the complete chromatic number of Halin graphs 总被引:8,自引:0,他引:8
ThisresearchissupportedbytheNationalNaturalScienceFoundationofChina.Write.1.IntroductionDefinition1.FOrany3-connectedplanargraphG(V,E,F)withA(G)23,iftheboundaryedgesoffacefowhichisadjacenttotheothersareremoved,itbecomesatree,andthedegreeofeachvertexofV(fo)is3,andthenGiscalledaHalingraph;foiscalledtheouterfaceofG,andtheotherscalledtheinteriorfaces,thevenicesonthefacefoarecalledtheoutervenices,theoillersarecalledtheinterior...ti..,tll.ForanyplanargraphG(V,E,F),f,f'eF,fisadjacenttof'ifan… 相似文献