共查询到20条相似文献,搜索用时 23 毫秒
1.
2.
3.
Manu Basavaraju 《Discrete Mathematics》2008,308(24):6650-6653
An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors. 相似文献
4.
A proper -edge-coloring of a graph with colors in is neighbor sum distinguishing (or, NSD for short) if for any two adjacent vertices, the sums of the colors of the edges incident with each of them are distinct. Flandrin et al. conjectured that every connected graph with at least vertices has an NSD edge coloring with at most colors. Huo et al. proved that every subcubic graph without isolated edges has an NSD -edge-coloring. In this paper, we first prove a structural result about subcubic graphs by applying the decomposition theorem of Trotignon and Vu?kovi?, and then applying this structural result and the Combinatorial Nullstellensatz, we extend the NSD -edge-coloring result to its list version and show that every subcubic graph without isolated edges has a list NSD -edge-coloring. 相似文献
5.
6.
Xuding Zhu 《Discrete Applied Mathematics》2009,157(4):710-714
A graph is subcubic if its maximum degree is at most 3. The bipartite density of a graph G is defined as b(G)=max{|E(B)|/|E(G)|:B is a bipartite subgraph of G}. It was conjectured by Bondy and Locke that if G is a triangle-free subcubic graph, then and equality holds only if G is in a list of seven small graphs. The conjecture has been confirmed recently by Xu and Yu. This note gives a shorter proof of this result. 相似文献
7.
The acyclic matching number of a graph is the largest size of an acyclic matching in , that is, a matching in such that the subgraph of induced by the vertices incident to edges in is a forest. We show that the acyclic matching number of a connected subcubic graph with edges is at least except for two graphs of order 5 and 6. 相似文献
8.
Ghurumuruhan Ganesan 《Discrete Mathematics》2021,344(9):112475
9.
Boris Brimkov Jennifer Edmond Robert Lazar Bernard Lidický Kacy Messerschmidt Shanise Walker 《Discrete Mathematics》2017,340(10):2538-2549
An injective coloring of a graph is an assignment of colors to the vertices of so that any two vertices with a common neighbor have distinct colors. A graph is injectively -choosable if for any list assignment , where for all , has an injective -coloring. Injective colorings have applications in the theory of error-correcting codes and are closely related to other notions of colorability. In this paper, we show that subcubic planar graphs with girth at least 6 are injectively 5-choosable. This strengthens the result of Lu?ar, ?krekovski, and Tancer that subcubic planar graphs with girth at least 7 are injectively 5-colorable. Our result also improves several other results in particular cases. 相似文献
10.
Recently, Balogh et al. (2018) answered in negative the question that was posed in several earlier papers whether the packing chromatic number is bounded in the class of graphs with maximum degree 3. In this note, we present an explicit infinite family of subcubic graphs with unbounded packing chromatic number. 相似文献
11.
ε_n表示n个顶点欧拉图的集合.通过对欧拉图hyper-Wiener指标性质的研究,刻画了ε_n中具有最小和最大hyper-Wiener指标的极图. 相似文献
12.
Andrzej Czygrinow 《Discrete Mathematics》2004,286(3):219-223
For a graph G=(V(G),E(G)), a strong edge coloring of G is an edge coloring in which every color class is an induced matching. The strong chromatic index of G, χs(G), is the smallest number of colors in a strong edge coloring of G. The strong chromatic index of the random graph G(n,p) was considered in Discrete Math. 281 (2004) 129, Austral. J. Combin. 10 (1994) 97, Austral. J. Combin. 18 (1998) 219 and Combin. Probab. Comput. 11 (1) (2002) 103. In this paper, we consider χs(G) for a related class of graphs G known as uniform or ε-regular graphs. In particular, we prove that for 0<ε?d<1, all (d,ε)-regular bipartite graphs G=(U∪V,E) with |U|=|V|?n0(d,ε) satisfy χs(G)?ζ(ε)Δ(G)2, where ζ(ε)→0 as ε→0 (this order of magnitude is easily seen to be best possible). Our main tool in proving this statement is a powerful packing result of Pippenger and Spencer (Combin. Theory Ser. A 51(1) (1989) 24). 相似文献
13.
A set of vertices in a graph is an independent dominating set of if is an independent set and every vertex not in is adjacent to a vertex in . The independent domination number, , of is the minimum cardinality of an independent dominating set. In this paper, we extend the work of Henning, Löwenstein, and Rautenbach (2014) who proved that if is a bipartite, cubic graph of order and of girth at least , then . We show that the bipartite condition can be relaxed, and prove that if is a cubic graph of order and of girth at least , then . 相似文献
14.
Ginette Gauyacq 《Discrete Applied Mathematics》1997,80(2-3):149-160
We present a technique for building, in some Cayley graphs, a routing for which the load of every edge is almost the same. This technique enables us to find the edge-forwarding index of star graphs and complete-transposition graphs. 相似文献
15.
16.
17.
18.
The star chromatic index of a mulitigraph , denoted , is the minimum number of colors needed to properly color the edges of such that no path or cycle of length four is bi-colored. A multigraph is star-edge-colorable if . Dvo?ák et al. (2013) proved that every subcubic multigraph is star 7-edge-colorable, and conjectured that every subcubic multigraph should be star 6-edge-colorable. Kerdjoudj, Kostochka and Raspaud considered the list version of this problem for simple graphs and proved that every subcubic graph with maximum average degree less than is star list-5-edge-colorable. It is known that a graph with maximum average degree is not necessarily star 5-edge-colorable. In this paper, we prove that every subcubic multigraph with maximum average degree less than is star 5-edge-colorable. 相似文献
19.
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. 相似文献
20.
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 相似文献