Search

For a proper k -edge coloring ϕ : E (G) → { 1 , 2 , ... , k } of a graph G , let w (v) denote the sum of the colors taken on the edges incident to the vertex v. Given a positive integer p , the Σ p -neighbor sum distinguishing k -edge coloring of G is ϕ such that for each edge u v ∈ E (G) , | w (v) − w (u) | ≥ p. We denote the smallest integer k in such coloring of G by χ Σ p ′ (G). For p = 1 , Wang et al. proved that χ Σ 1 ′ (G) ≤ max { Δ (G) + 1 0 , 2 5 }. In this paper, we show that if G is a planar graph without isolated edges, then χ Σ p ′ (G) ≤ max { Δ (G) + (1 6 p − 6) , f (p) } , where f (p) = max { 2 2 p + 3 , 8 p 2 + 2 6 p + 1 + (2 p + 1) 1 6 p 2 + 9 6 p − 1 5 4 }. [ABSTRACT FROM AUTHOR]

A (k , d) -list assignment L of a graph G is a mapping that assigns to each vertex v a list L (v) of at least k colors satisfying | L (x) ∩ L (y) | ≤ d for each edge x y. A graph G is (k , d) -choosable if there exists an L -coloring of G for every (k , d) -list assignment L. This concept is also known as choosability with separation. In this paper, we prove that any planar graph G is (3 , 1) -choosable if any i -cycle is not adjacent to a j -cycle, where 5 ≤ i ≤ 6 and 5 ≤ j ≤ 7. [ABSTRACT FROM AUTHOR]

Let $$G=(V,E)$$ be a graph and $$\phi :V\cup E\rightarrow \{1,2,\ldots ,k\}$$ be a total coloring of G. Let C( v) denote the set of the color of vertex v and the colors of the edges incident with v. Let f( v) denote the sum of the color of vertex v and the colors of the edges incident with v. The total coloring $$\phi $$ is called neighbor set distinguishing or adjacent vertex distinguishing if $$C(u)\ne C(v)$$ for each edge $$uv\in E(G)$$ . We say that $$\phi $$ is neighbor sum distinguishing if $$f(u)\ne f(v)$$ for each edge $$uv\in E(G)$$ . In both problems the challenging conjectures presume that such colorings exist for any graph G if $$k\ge \varDelta (G)+3$$ . In this paper, by using the famous Combinatorial Nullstellensatz, we prove that in both problems $$k\ge \varDelta (G)+2\mathrm{col}(G)-2$$ is sufficient, moreover we prove that if G is not a forest and $$\varDelta \ge 4$$ , then $$k\ge \varDelta (G)+2\mathrm{col}(G)-3$$ is sufficient, where $$\mathrm{col}(G)$$ is the coloring number of G. In fact we prove these results in their list versions, which improve the previous results. As a consequence, we obtain an upper bound of the form $$\varDelta (G)+C$$ for some families of graphs, e.g. $$\varDelta +9$$ for planar graphs. In particular, we therefore obtain that when $$\varDelta \ge 4$$ two conjectures we mentioned above hold for 2-degenerate graphs (with coloring number at most 3) in their list versions. [ABSTRACT FROM AUTHOR]

Let $$G$$ be a planar graph with $$\varDelta \ge 8$$ and $$v$$ be a vertex of $$G$$ . It is proved that $$\chi ''(G)=\varDelta +1$$ if $$v$$ is not incident with chordal $$5$$ - or $$6$$ -cycles by Shen et al. (Appl Math Lett 22:1369-1373, ), or $$v$$ is not incident with $$2$$ -chordal $$5$$ -cycle by Chang et al. (Theor Comput Sci 476:16-23, ). In this paper we generalize these results and prove that if $$v$$ is not incident with chordal $$6$$ -cycle, or chordal $$7$$ -cycle, or $$2$$ -chordal $$5$$ -cycle, then $$\chi ''(G)=\varDelta +1$$ . [ABSTRACT FROM AUTHOR]

A $$k$$ -total-coloring of a graph $$G$$ is a coloring of vertex set and edge set using $$k$$ colors such that no two adjacent or incident elements receive the same color. In this paper, we prove that if $$G$$ is a planar graph with maximum $$\Delta \ge 8$$ and every 6-cycle of $$G$$ contains at most one chord or any chordal 6-cycles are not adjacent, then $$G$$ has a $$(\Delta +1)$$ -total-coloring. [ABSTRACT FROM AUTHOR]

Graph coloring is an important tool in the study of optimization, computer science, network design, e.g., file transferring in a computer network, pattern matching, computation of Hessians matrix and so on. In this paper, we consider one important coloring, vertex coloring of a total graph, which is familiar to us by the name of 'total coloring'. Total coloring is a coloring of $$V\cup {E}$$ such that no two adjacent or incident elements receive the same color. In other words, total chromatic number of $$G$$ is the minimum number of disjoint vertex independent sets covering a total graph of $$G$$ . Here, let $$G$$ be a planar graph with $$\varDelta \ge 8$$ . We proved that if for every vertex $$v\in V$$ , there exists two integers $$i_{v},j_{v} \in \{3,4,5,6,7,8\}$$ such that $$v$$ is not incident with intersecting $$i_v$$ -cycles and $$j_v$$ -cycles, then the vertex chromatic number of total graph of $$G$$ is $$\varDelta +1$$ , i.e., the total chromatic number of $$G$$ is $$\varDelta +1$$ . [ABSTRACT FROM AUTHOR]

The linear arboricity la( G) of a graph G is the minimum number of linear forests which partition the edges of G. In this paper, it is proved that for a planar graph G, $${la(G)=\lceil\frac{\Delta(G)}{2}\rceil}$$ if Δ( G) ≥ 7 and G has no 5-cycles with chords, or Δ( G) ≥ 5 and G has no 5-, 6-cycles with chords. [ABSTRACT FROM AUTHOR]

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that each 1-planar graph with maximum degree Δ is (Δ+1)-edge-choosable and (Δ+2)-total-choosable if Δ ⩾ 16, and is Δ-edge-choosable and (Δ+1)-total-choosable if Δ ⩾ 21. The second conclusion confirms the list coloring conjecture for the class of 1-planar graphs with large maximum degree. [ABSTRACT FROM AUTHOR]

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′( G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′( G) ≤ Δ( G) + 2 for any graphs. In this paper, it is shown that the conjecture holds for planar graphs without 4- and 5-cycles or without 4- and 6-cycles. [ABSTRACT FROM AUTHOR]

Abstract: A proper vertex coloring of a graph G is equitable if the size of color classes differ by at most one. The equitable chromatic threshold of G, denoted by , is the smallest integer m such that G is equitably n-colorable for all . We prove that if G is a non-bipartite planar graph with girth and or G is a 2-connected outerplanar graph with girth . [Copyright &y& Elsevier]

Let G be a connected simple graph with at least one edge. The hypergraph H = H (G) with the same vertex set as G whose hyper-edges are the maximal cliques of G is called the clique-hypergraph of G. A list-assignment of G is a function L which assigns to each vertex v ∈ V (G) a set L (v) (called the list of v). A k -list-assignment of G is a list-assignment L such that L (v) has at least k elements for every v ∈ V (G). For a given list assignment L , a list-coloring of H (G) is a function c : V (G) → ∪ v L (v) such that c (v) ∈ L (v) for every v ∈ V (G) and no hyper-edge of H (G) is monochromatic. A list-coloring of H (G) is strong if no 3-cycle of G is monochromatic. H (G) is (strongly) k -choosable if, for every k -list assignment L , there exists a (strong) list-coloring of H (G). Mohar and S ˇ krekovski proved that the clique-hypergraphs of planar graphs are strongly 4-choosable (Electr. J. Combin. 6 (1999), #R26). In this paper we give a short proof of the result and present a linear time algorithm for the strong list-4-coloring of H (G) if G is a planar graph. In addition, we prove that H (G) is strongly 4-choosable if G is a K 5 -minor-free graph, which is a generalization of their result. [ABSTRACT FROM AUTHOR]

Abstract Let k be a positive integer. An adjacent vertex distinguishing (for short, AVD) total- k -coloring of a graph G is a proper total- k -coloring of G such that any two adjacent vertices have different color sets, where the color set of a vertex v contains the color of v and the colors of its incident edges. It was conjectured that any graph with maximum degree Δ has an AVD total-(Δ + 3)-coloring. The conjecture was confirmed for any graph with maximum degree at most 4 and any planar graph with maximum degree at least 10. In this paper, we verify the conjecture for all planar graphs with maximum degree at least 9. Moreover, we prove that any planar graph with maximum degree at least 10 has an AVD total-(Δ + 2)-coloring and the bound Δ + 2 is sharp. [ABSTRACT FROM AUTHOR]

Let c be a proper total coloring of a graph G = ( V , E ) with integers 1 , 2 , … , k . For any vertex v ∈ V ( G ) , let ∑ c ( v ) denote the sum of colors of the edges incident with v and the color of v . If for each edge u v ∈ E ( G ) , ∑ c ( u ) ≠ ∑ c ( v ) , then such a total coloring is said to be neighbor sum distinguishing. The least k for which such a coloring of G exists is called the neighbor sum distinguishing total chromatic number and denoted by χ Σ ″ ( G ) . Pilśniak and Woźniak conjectured χ Σ ″ ( G ) ≤ Δ ( G ) + 3 for any simple graph with maximum degree Δ ( G ) . It is known that this conjecture holds for any planar graph with Δ ( G ) ≥ 13 . In this paper, we prove that for any planar graph, χ Σ ″ ( G ) ≤ max ⁡ { Δ ( G ) + 3 , 14 } . [ABSTRACT FROM AUTHOR]

Abstract: Let G be a planar graph with and without adjacent cycles of size i and j, for some . In this paper, it is proved that G is -total-colorable. [Copyright &y& Elsevier]

Given a simple graph G , a proper total- k -coloring ϕ : V ( G ) ∪ E ( G ) → { 1 , 2 , … , k } is called neighbor sum distinguishing if S ϕ ( u ) ≠  S ϕ ( v ) for any two adjacent vertices u, v  ∈  V ( G ), where S ϕ ( u ) is the sum of the color of u and the colors of the edges incident with u . It has been conjectured by Pilśniak and Woźniak that Δ ( G ) + 3 colors enable the existence of a neighbor sum distinguishing total coloring. The conjecture is confirmed for any graph with maximum degree at most 3 and for planar graph with maximum degree at least 11. We prove that the conjecture holds for any planar graph G with Δ ( G ) = 10 . Moreover, for any planar graph G with Δ( G ) ≥ 11, Δ ( G ) + 2 colors guarantee such a total coloring, and the upper bound Δ ( G ) + 2 is tight. [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]

Let G = (V , E) be a simple graph and ϕ : E (G) → { 1 , 2 , ... , k } be a proper k -edge coloring of G. We say that ϕ is neighbor sum (set) distinguishing if for each edge u v ∈ E (G) , the sum (set) of colors taken on the edges incident with u is different from the sum (set) of colors taken on the edges incident with v. The smallest k such that G has a neighbor sum (set) distinguishing k -edge coloring is called the neighbor sum (set) distinguishing index of G and denoted by χ ∑ ′ (G) ( χ a ′ (G)). It was conjectured that if G is a connected graph and G ∉ { K 2 , C 5 } , then χ ∑ ′ (G) ≤ Δ (G) + 2 and χ a ′ (G) ≤ Δ (G) + 2. For a given graph G , let (L e) e ∈ E be a set of lists of real numbers and each list has size k. The smallest k such that for any specified collection of such lists there exists a neighbor sum (set) distinguishing edge coloring using colors from L e for each e ∈ E is called the list neighbor sum (set) distinguishing index of G , and denoted by ch ∑ ′ (G) (ch a ′ (G)). In this paper, we prove that if G is a planar graph with Δ (G) ≥ 22 and with no isolated edges, then ch ∑ ′ (G) ≤ Δ (G) + 6 and ch a ′ (G) ≤ Δ (G) + 3. This improves a result by Przybyło and Wong (Przybyło and Wong, 2015), which states that if G is a planar graph without isolated edges, then ch ∑ ′ (G) ≤ Δ (G) + 13 (so ch a ′ (G) ≤ Δ (G) + 13 also holds). Our approach is based on the Combinatorial Nullstellensatz and the discharging method. [ABSTRACT FROM AUTHOR]