共查询到20条相似文献,搜索用时 0 毫秒
1.
《Journal of Graph Theory》2018,88(4):566-576
The star chromatic index of a multigraph G, denoted , is the minimum number of colors needed to properly color the edges of G such that no path or cycle of length four is bicolored. A multigraph G is star k‐edge‐colorable if . Dvořák, Mohar, and Šámal [Star chromatic index, J. Graph Theory 72 (2013), 313–326] proved that every subcubic multigraph is star 7‐edge‐colorable. They conjectured in the same article that every subcubic multigraph should be star 6‐edge‐colorable. In this article, we first prove that it is NP‐complete to determine whether for an arbitrary graph G. This answers a question of Mohar. We then establish some structure results on subcubic multigraphs G with such that but for any , where . We finally apply the structure results, along with a simple discharging method, to prove that every subcubic multigraph G is star 6‐edge‐colorable if , and star 5‐edge‐colorable if , respectively, where is the maximum average degree of a multigraph G. This partially confirms the conjecture of Dvořák, Mohar, and Šámal. 相似文献
2.
3.
4.
5.
In this paper the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows:let m = m(n) be a positive integer-valued function on n and ζ(n,m;{pk}) the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A ={a1,a2,...,an} and B = {b1,b2,...,bm}, in which the numbers tai,bj of the edges between any two vertices ai∈A and bj∈ B are identically distributed independent random variables with distribution P{tai,bj=k}=pk,k=0,1,2,...,where pk ≥0 and ∞Σk=0 pk=1. They obtain that Xc,d,A, the number of vertices in A with degree between c and d of Gn,m∈ζ(n, m;{pk}) has asymptotically Poisson distribution, and answer the following two questions about the space ζ(n,m;{pk}) with {pk} having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for {pk} can there be a function D(n) such that almost every random multigraph Gn,m∈ζ(n,m;{pk}) has maximum degree D(n)in A? under which condition for {pk} has almost every multigraph G(n,m)∈ζ(n,m;{pk}) a unique vertex of maximum degree in A? 相似文献
6.
Douglas R. Woodall 《Journal of Graph Theory》2019,91(2):103-121
A graph is here called 3- critical if , and for every edge of . The 3-critical graphs include (the Petersen graph with a vertex deleted), and subcubic graphs that are Hajós joins of copies of . Building on a recent paper of Cranston and Rabern, it is proved here that if is 3-critical and not nor a Hajós join of two copies of , then has average degree at least ; this bound is sharp, as it is the average degree of a Hajós join of three copies of . 相似文献
7.
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. 相似文献
8.
A strong -edge-coloring of a graph G is an edge-coloring with colors in which every color class is an induced matching. The strong chromatic index of , denoted by , is the minimum for which has a strong -edge-coloring. In 1985, Erd?s and Ne?et?il conjectured that , where is the maximum degree of . When is a graph with maximum degree at most 3, the conjecture was verified independently by Andersen and Horák, Qing, and Trotter. In this paper, we consider the list version of strong edge-coloring. In particular, we show that every subcubic graph has strong list-chromatic index at most 11 and every planar subcubic graph has strong list-chromatic index at most 10. 相似文献
9.
A star edge-coloring of a graph is a proper edge coloring such that every 2-colored connected subgraph of is a path of length at most 3. For a graph , let the list star chromatic index of , , be the minimum such that for any -uniform list assignment for the set of edges, has a star edge-coloring from . Dvo?ák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph is less than (resp. 3), then (resp. ). 相似文献
10.
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. 相似文献
11.
A star k-edge-coloring is a proper k-edge-coloring such that every connected bicolored subgraph is a path of length at most 3.The star chromatic indexχ'st(G)of a graph G is the smallest integer k such that G has a star k-edge-coloring.The list star chromatic index ch'st(G)is defined analogously.The star edge coloring problem is known to be NP-complete,and it is even hard to obtain tight upper bound as it is unknown whether the star chromatic index for complete graph is linear or super linear.In this paper,we study,in contrast,the best linear upper bound for sparse graph classes.We show that for everyε>0 there exists a constant c(ε)such that if mad(G)<8/3-ε,then■and the coefficient 3/2 ofΔis the best possible.The proof applies a newly developed coloring extension method by assigning color sets with different sizes. 相似文献
12.
13.
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. 相似文献
14.
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. 相似文献
15.
Eckhard Steffen 《Journal of Graph Theory》2001,36(1):24-34
The circular flow number Fc(G) of a graph G = (V, E) is the minimum r ϵ ℚ such that G admits a flow ϕ with 1 ≤ ϕ (e) ≤ r − 1, for each e ϵ E. We determine the circular flow number of some regular multigraphs. In particular, we characterize the bipartite (2t+1)‐regular graphs (t ≥ 1). Our results imply that there are gaps for possible circular flow numbers for (2t+1)‐regular graphs, e.g., there is no cubic graph G with 3 < Fc(G) < 4. We further show that there are snarks with circular flow number arbitrarily close to 4, answering a question of X. Zhu. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 24–34, 2001 相似文献
16.
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. 相似文献
17.
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. 相似文献
18.
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 相似文献
19.
A star edge-coloring of a graph is a proper edge-coloring without bichromatic paths and cycles of length four. In this paper, we consider the list version of this coloring and prove that the list star chromatic index of every subcubic graph is at most 7, answering the question of Dvořák et al (J Graph Theory, 72 (2013), 313-326). 相似文献
20.