Search

A labeling of a digraph D with m arcs is a bijection from the set of arcs of D to {1,...,m}. A labeling of D is antimagic if no two vertices in D have the same vertex‐sum, where the vertex‐sum of a vertex u∈V(D) for a labeling is the sum of labels of all arcs entering u minus the sum of labels of all arcs leaving u. Motivated by the conjecture of Hartsfield and Ringel from 1990 on antimagic labelings of graphs, Hefetz, Mütze, and Schwartz [On antimagic directed graphs, J. Graph Theory 64 (2010) 219–232] initiated the study of antimagic labelings of digraphs, and conjectured that every connected graph admits an antimagic orientation, where an orientation D of a graph G is antimagic if D has an antimagic labeling. It remained unknown whether every disjoint union of cycles admits an antimagic orientation. In this article, we first answer this question in the positive by proving that every 2‐regular graph has an antimagic orientation. We then show that for any integer d≥2, every connected, 2d‐regular graph has an antimagic orientation. Our technique is new. [ABSTRACT FROM AUTHOR]

The famous Ryser Conjecture states that there is a transversal of size n in a latin square of odd order n , which is equivalent to finding a rainbow matching of size n in a properly edge-colored K n , n when n is odd. Let δ denote the minimum degree of a graph. In 2011, Wang proposed a more general question to find a function f ( δ ) ( f ( δ ) ≥ 2 δ + 1 ) such that for each properly edge-colored graph of order f ( δ ) , there exists a rainbow matching of size δ . The best bound so far is f ( δ ) ≤ 3.5 δ + 2 due to Lo. Babu et al. considered this problem in strongly edge-colored graphs in which each path of length 3 is rainbow. They proved that if G is a strongly edge-colored graph of order at least 2 ⌊ 3 δ 4 ⌋ , then G has a rainbow matching of size ⌊ 3 δ 4 ⌋ . They proposed an interesting question: Is there a constant c greater than 3 4 such that every strongly edge-colored graph G has a rainbow matching of size at least c δ if | V ( G ) | ≥ 2 ⌊ c δ ⌋ ? Clearly, c ≤ 1 . We prove that if G is a strongly edge-colored graph with minimum degree δ and order at least 2 δ + 2 , then G has a rainbow matching of size δ . [ABSTRACT FROM AUTHOR]

A proper [ k]-edge coloring of a graph G is a proper edge coloring of G using colors from $$[k]=\{1,2,\ldots ,k\}$$ . A neighbor sum distinguishing [ k]-edge coloring of G is a proper [ k]-edge coloring of G such that for each edge $$uv\in E(G)$$ , the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. By nsdi( G), we denote the smallest value k in such a coloring of G. It was conjectured by Flandrin et al. that if G is a connected graph with at least three vertices and $$G\ne C_5$$ , then nsdi $$(G)\le \varDelta (G)+2$$ . In this paper, we prove that this conjecture holds for $$K_4$$ -minor free graphs, moreover if $$\varDelta (G)\ge 5$$ , we show that nsdi $$(G)\le \varDelta (G)+1$$ . The bound $$\varDelta (G)+1$$ is sharp. [ABSTRACT FROM AUTHOR]

A proper edge- k-coloring of a graph G is an assignment of k colors $$1,2,\ldots ,k$$ to the edges of G such that no two adjacent edges receive the same color. A neighbor sum distinguishing edge- k-coloring of G is a proper edge- k-coloring of G such that for each edge $$uv\in E(G)$$ , the sum of colors taken on the edges incident with u is different from the sum of colors taken on the edges incident with v. By $${ {ndi}}_{\sum }(G)$$ , we denote the smallest value k in such a coloring of G. The maximum average degree of G is $${ {mad}}(G)=\max \{2|E(H)|/|V(H)|\}$$ , where the maximum is taken over all the non-empty subgraphs H of G. In this paper, we obtain that if G is a graph without isolated edges and $${ {mad}}(G)<8/3$$ , then $${ {ndi}}_{\sum }(G)\le k$$ where $$k=\max \{\Delta (G)+1,6\}$$ . It partially confirms the conjecture proposed by Flandrin et al. (Graphs Comb 29:1329-1336, ). [ABSTRACT FROM AUTHOR]

The famous 1-2-3 conjecture due to Karoński, Łuczak and Thomason states that the edges of any nice graph (without a component isomorphic to $$K_{2}$$ ) may be weighted from the set {1,2,3} so that the vertices are properly coloured by the sums of their incident edge weights. Bartnicki, Grytczuk and Niwcyk introduced its list version. Assign to each edge $$e\in E(G)$$ a list of $$k$$ real numbers, say $$L(e)$$ , and choose a weight $$w(e)\in L(e)$$ for each $$e \in E(G)$$ . The resulting function $$w: E(G)\rightarrow \bigcup _{e\in E(G)}L(e)$$ is called an edge $$k$$ -list-weighting. Given a graph $$G$$ , the smallest $$k$$ such that any assignment of lists of size $$k$$ to $$E(G)$$ permits an edge $$k$$ -list-weighting which is a vertex coloring by sums is denoted by $$ch^{e}_{\Sigma }(G)$$ and called the edge weight choosability of $$G$$ . Bartnicki, Grytczuk and Niwcyk conjectured that if $$G$$ is a nice graph, then $$ch^{e}_{\Sigma }(G)\le 3$$ . There is no known constant $$K$$ such that $$ch^{e}_{\Sigma }(G) \le K$$ for any nice graph $$G$$ . Fu et al. proved that for a nice graph $$G$$ with maximum degree $$\Delta (G)$$ , $$ch^{e}_{\Sigma }(G)\le \lceil \frac{3\Delta (G)}{2}\rceil $$ . In this paper, we improve this bound to $$\lceil \frac{4\Delta (G)+8}{3}\rceil $$ . [ABSTRACT FROM AUTHOR]

Let G be a graph, and let f be an integer function on V with $${1\leq f(v)\leq d(v)}$$ to each vertex $${\upsilon \in V}$$. An f-edge cover coloring is a coloring of edges of E( G) such that each color appears at each vertex $${\upsilon \in V(G)}$$ at least f( υ) times. The maximum number of colors needed to f-edge cover color G is called the f-edge cover chromatic index of G and denoted by $${\chi^{'}_{fc}(G)}$$. It is well known that any simple graph G has the f-edge cover chromatic index equal to δ( G) or δ( G) − 1, where $${\delta_{f}(G)=\,min\{\lfloor \frac{d(v)}{f(v)} \rfloor: v\in V(G)\}}$$. The fractional f-edge cover chromatic index of a graph G, denoted by $${\chi^{'}_{fcf}(G)}$$, is the fractional f-matching number of the edge f-edge cover hypergraph $${\mathcal{H}}$$ of G whose vertices are the edges of G and whose hyperedges are the f-edge covers of G. In this paper, we give an exact formula of $${\chi^{'}_{fcf}(G)}$$ for any graph G, that is, $${\chi^{'}_{fcf}(G)=\,min \{\min\limits_{v\in V(G)}d_{f}(v), \lambda_{f}(G)\}}$$, where $${\lambda_{f}(G)=\min\limits_{S} \frac{|C[S]|}{\lceil (\sum\limits_{v\in S}{f(v)})/2 \rceil}}$$ and the minimum is taken over all nonempty subsets S of V( G) and C[ S] is the set of edges that have at least one end in S. [ABSTRACT FROM AUTHOR]

A proper t-coloring of a graph G is a mapping $${\varphi: V(G) \rightarrow [1, t]}$$ such that $${\varphi(u) \neq \varphi(v)}$$ if u and v are adjacent vertices, where t is a positive integer. The chromatic number of a graph G, denoted by $${\chi(G)}$$ , is the minimum number of colors required in any proper coloring of G. A linear t-coloring of a graph is a proper t-coloring such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number of a graph G, denoted by $${lc(G)}$$ , is the minimum t such that G has a linear t-coloring. In this paper, the linear t-colorings of Sierpiński-like graphs S( n, k), $${S^+(n, k)}$$ and $${S^{++}(n, k)}$$ are studied. It is obtained that $${lc(S(n, k))= \chi (S(n, k)) = k}$$ for any positive integers n and k, $${lc(S^+(n, k)) = \chi(S^+(n, k)) = k}$$ and $${lc(S^{++}(n, k)) = \chi(S^{++}(n, k)) = k}$$ for any positive integers $${n \geq 2}$$ and $${k \geq 3}$$ . Furthermore, we have determined the number of paths and the length of each path in the subgraph induced by the union of any two color classes completely. [ABSTRACT FROM AUTHOR]

Abstract: A proper -edge coloring of a graph is a proper edge coloring of using colors of the set , where . A neighbor sum distinguishing -edge coloring of is a proper -edge coloring of such that, for each edge , the sum of colors taken on the edges incident with is different from the sum of colors taken on the edges incident with . By , we denote the smallest value in such a coloring of . The average degree of a graph is ; we denote it by . The maximum average degree of is the maximum of average degrees of its subgraphs. In this paper, we show that, if is a graph without isolated edges and , then , where . This partially confirms the conjecture proposed by Flandrin et al. [Copyright &y& Elsevier]

Abstract: Given a graph and an edge-coloring of , a heterochromatic cycle of is a cycle in which any pair of edges have distinct colors. Let , named the color degree of a vertex , be defined as the maximum number of edges incident with that have distinct colors. In this paper, some color degree conditions for the existence of heterochromatic cycles are obtained. [Copyright &y& Elsevier]

Let D be a digraph. The circular chromatic number $${\chi_c(D)}$$ and chromatic number $${\chi(D)}$$ of D were proposed recently by Bokal et al. Let $${\vec{\chi_c}(G)={\rm max}\{\chi_c(D)| D\, {\rm is\, an\, orientation\, of} G\}}$$. Let G be a planar graph and n ≥ 2. We prove that if the girth of G is at least $${\frac{10n-5}{3},}$$ then $${\vec{\chi_c}(G)\leq \frac{n}{n-1}}$$. We also study the circular chromatic number of some special planar digraphs. [ABSTRACT FROM AUTHOR]

Let G be an edge-colored graph. A heterochromatic cycle of G is a cycle in which any pair of edges have distinct colors. Let d( v), named the color degree of a vertex v, be defined as the maximum number of edges incident with v, that have distinct colors. In this paper, we prove that if G is an edge-colored triangle-free graph of order n ≥ 9 and $${d^c(v) \geq \frac{(3-\sqrt{5})n}{2}+1}$$ for each vertex v of G, G has a heterochromatic C. [ABSTRACT FROM AUTHOR]

Abstract: A proper edge coloring of is -acyclic if every cycle contained in is colored with at least colors. The -acyclic chromatic index of a graph, denoted by , is the minimum number of colors required to produce an -acyclic edge coloring. In this paper, we study 4-acyclic edge colorings by proving that for every planar graph, for every series–parallel graph and for every outerplanar graph. In addition, we prove that every planar graph with maximum degree at least and girth at least has for every . [Copyright &y& Elsevier]

Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let δ denote the minimum degree of G. We show that if | V( G)| > ( δ + 14 δ + 1)/4, then G has a rainbow matching of size δ, which answers a question asked by G. Wang [Electron. J. Combin., 2011, 18: #N162] affirmatively. In addition, we prove that if G is a properly colored bipartite graph with bipartition ( X, Y) and max{| X|, | Y|} > ( δ + 4 δ − 4)/4, then G has a rainbow matching of size δ. [ABSTRACT FROM AUTHOR]

Abstract: The vertex arboricity of graph is defined as the minimum of subsets in a partition of the vertex set of so that each subset induces an acyclic subgraph and has been widely studied. We define the concept of circular vertex arboricity of graph , which is a natural generalization of vertex arboricity. We give some basic properties of circular vertex arboricity and study the circular vertex arboricity of planar graphs. [Copyright &y& Elsevier]

Abstract: Let be an edge-colored graph. An alternating cycle of is a cycle of in which any two consecutive edges have distinct colors. Let , the color degree of a vertex , be defined as the maximum number of edges incident with that have distinct colors. In this paper, we study color degree conditions for the existence of alternating cycles of prescribed length. [Copyright &y& Elsevier]

Abstract: A proper -edge coloring of a graph is a proper edge coloring of using colors from . A neighbor sum distinguishing -edge coloring of is a proper -edge coloring of such that for each edge , the sum of colors taken on the edges incident to is different from the sum of colors taken on the edges incident to . By , we denote the smallest value in such a coloring of . It was conjectured by Flandrin et al. that if is a connected graph with at least three vertices and , then . They gave an upper bound : when . In this paper, we show that , which improves the previous bound when . [Copyright &y& Elsevier]

Abstract A k -antimagic labeling of a digraph D with n vertices and m arcs is an injection from the set of arcs of D to the integers { 1 , ... , m + k } such that all n vertex-sums are pairwise distinct, where the vertex-sum of a vertex v is the sum of labels of all arcs entering v minus the sum of labels of all arcs leaving v. An orientation D of a graph G is called k -antimagic if D has a k -antimagic labeling. Hefetz et al. (2010) conjectured that every connected graph admits an antimagic orientation, where "antimagic" is short for "0-antimagic". In this paper, we consider local k -antimagic orientations of graphs. An orientation D of a graph G is called local k -antimagic if there is an injective edge labeling from E (G) to { 1 , ... , | E (G) | + k } such that any two adjacent vertices of D have different vertex-sums. We prove that every d -degenerate graph admits a local (d + 2) -antimagic orientation. [ABSTRACT FROM AUTHOR]

Abstract A graph G is (k , k ′) -choosable if the following holds: For any list assignment L which assigns to each vertex v a set L (v) of k real numbers, and assigns to each edge e a set L (e) of k ′ real numbers, there is a total weighting ϕ : V (G) ∪ E (G) → R such that ϕ (z) ∈ L (z) for z ∈ V ∪ E , and ∑ e ∈ E (u) ϕ (e) + ϕ (u) ≠ ∑ e ∈ E (v) ϕ (e) + ϕ (v) for every edge u v. This paper proves that if G is a connected graph of maximum degree Δ ≥ 2 , then G is (1 , Δ + 1) -choosable. [ABSTRACT FROM AUTHOR]

In this paper, we prove for planar graphGwith maximum degree Δ ≥ 12 that the (2,1)-total labelling numberλ2(G) is at most Δ + 2. [ABSTRACT FROM PUBLISHER]

A neighbor sum distinguishing edge- k -coloring, or nsd- k -coloring for short, of a graph G is a proper edge coloring of G with elements from { 1 , 2 , … , k } such that no pair of adjacent vertices meets the same sum of colors of G . The definition of this coloring makes sense for graphs containing no isolated edges (we call such graphs normal). Let mad ( G ) and Δ ( G ) be the maximum average degree and the maximum degree of a graph G , respectively. In this paper, we prove that every normal graph with Δ ( G ) ≥ 5 and mad ( G ) < 3 admits an nsd- ( Δ ( G ) + 2 ) -coloring. Our approach is based on the Combinatorial Nullstellensatz and the discharging method. [ABSTRACT FROM AUTHOR]

A (proper) total [k]-coloring of a graph G is a mapping ϕ : V ( G ) ∪ E ( G ) → [ k ] = { 1 , 2 , … , k } such that any two adjacent elements in V ( G ) ∪ E ( G ) receive different colors. Let f ( v ) denote the sum of the color of a vertex v and the colors of all incident edges of v . A total [ k ] -neighbor sum distinguishing-coloring of G is a total [ k ] -coloring of G such that for each edge u v ∈ E ( G ) , f ( u ) ≠ f ( v ) . By χ n s d ″ ( G ) , we denote the smallest value k in such a coloring of G . In this paper, we show that if G is a planar graph with Δ ( G ) ≥ 14 , then χ n s d ″ ( G ) ≤ Δ ( G ) + 2 . [ABSTRACT FROM AUTHOR]

Abstract: In [23], Klavžar and Milutinović (1997) proved that there exist at most two different shortest paths between any two vertices in Sierpiński graphs , and showed that the number of shortest paths between any fixed pair of vertices of can be computed in . An almost-extreme vertex of , which was introduced in Klavžar and Zemljič (2013) [27], is a vertex that is either adjacent to an extreme vertex or incident to an edge between two subgraphs of isomorphic to . In this paper, we completely determine the set , where is any almost-extreme vertex of . [Copyright &y& Elsevier]

Abstract: A graph is equitably -choosable if, for any given -uniform list assignment , is -colorable and each color appears on at most vertices. A graph is said to be equitably -colorable if the vertex set can be partitioned into independent subsets such that . In this paper, we prove that every planar graph without -cycles is equitably -choosable and equitably -colorable where , which improves several recent results. [Copyright &y& Elsevier]

Abstract: Acyclic coloring problem is a specialized problem that arises in the efficient computation of Hessians. A proper edge coloring of a graph is called acyclic if there is no 2-colored cycle in . The acyclic chromatic index of , denoted by , is the least number of colors in an acyclic edge coloring of . Let be planar graphs with girth and maximum degree . In this paper, it is shown that if and , then ; if and or and , then . [Copyright &y& Elsevier]

Abstract: In this paper, we prove that -connected graphs have either a dominating path or two disjoint paths, wherein the length of the two paths is bounded by the minimum among and a parameter defined on the neighborhood condition of any four independent vertices of the graph. [Copyright &y& Elsevier]

A k -labeling of a graph G is an injective function ϕ from E ( G ) to m + k real numbers, where m = | E ( G ) | . Let μ G ( v ) = ∑ u v ∈ E ( G ) ϕ ( u v ) . A graph is called antimagic if G admits a 0-labeling with labels in { 1 , 2 , … , | E ( G ) | } such that μ G ( u ) ≠  μ G ( v ) for any pair u, v  ∈  V ( G ). A well-known conjecture of Hartsfield and Ringel states that every connected graph other than K 2 admits an antimagic labeling. Recently, two sets of authors Arumugam, Premalatha, Băca, Semanĭcová-Fen̆ov̆cíková, and Bensmail, Senhaji, Lyngsie independently introduced the weaker notion of a local antimagic labeling, which only distinguishes adjacent vertices by sum with labels in { 1 , 2 , … , | E ( G ) | } . Both sets of authors conjecture that any connected graph other than K 2 admits a local antimagic labeling. In this paper, we prove that every subcubic graph without isolated edges admits a local antimagic labeling with | E ( G )| positive real labels. We also prove that each graph G without isolated edges admits a local antimagic k -labeling, where k = min { Δ ( G ) + 1 , 3 c o l ( G ) + 3 2 } , and col ( G ) is the coloring number of G . Actually, the latter result holds for the list version. [ABSTRACT FROM AUTHOR]