Neighbor sum distinguishing total colorings of triangle free planar graphs

A total k-coloring c of a graph G is a proper total coloring c of G using colors of the set[k] = {1, 2,..., k}. Let f(u) denote the sum of the color on a vertex u and colors on all the edges incident to u. A k-neighbor sum distinguishing total coloring of G is a total k-coloring of G such that for each edge uv ∈ E(G), f(u) = f(v). By χ nsd(G), we denote the smallest value k in such a coloring of G. Pil′sniak and Wo′zniak conjectured that χ nsd(G) ≤Δ(G) + 3 for any simple graph with maximum degree Δ(G). In this paper, by using the famous Combinatorial Nullstellensatz, we prove that the conjecture holds for any triangle free planar graph with maximum degree at least 7.     

Total coloring of planar graphs without chordal 7-cycles

A k-total-coloring of a graph G is a coloring of vertices and edges of G using k colors such that no two adjacent or incident elements receive the same color.In this paper,it is proved that if G is a planar graph with Δ(G) ≥ 7 and without chordal 7-cycles,then G has a(Δ(G) + 1)-total-coloring.     

SOME APPLICATIONS OF PLANAR GRAPH IN KNOT THEORY

The relationship between a link diagram and its corresponding planar graph is briefly reviewed.A necessary and sufficient condition is given to detect when a planar graph corresponds to a knot.The rela...     

Planar Digraphs of Digirth Five Are 2‐Colorable

Neumann‐Lara (1985) and ?krekovski conjectured that every planar digraph with digirth at least three is 2‐colorable, meaning that the vertices can be 2‐colored without creating any monochromatic directed cycles. We prove a relaxed version of this conjecture: every planar digraph of digirth at least five is 2‐colorable. The result also holds in the setting of list colorings.     

Gromov hyperbolicity of planar graphs

We prove that under appropriate assumptions adding or removing an infinite amount of edges to a given planar graph preserves its non-hyperbolicity, a result which is shown to be false in general. In particular, we make a conjecture that every tessellation graph of ?² with convex tiles is non-hyperbolic; it is shown that in order to prove this conjecture it suffices to consider tessellation graphs of ?² such that every tile is a triangle and a partial answer to this question is given. A weaker version of this conjecture stating that every tessellation graph of ?² with rectangular tiles is non-hyperbolic is given and partially answered. If this conjecture were true, many tessellation graphs of ?² with tiles which are parallelograms would be non-hyperbolic.     

Longest cycles and their chords

Thomassen conjectured that any longest cycle of a 3-connected graph has a chord. In this paper, we will show that the conjecture is true for a planar graph if it is cubic or δ ? 4.     

Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz

Let G=(V,E)be a graph andφbe a total coloring of G by using the color set{1,2,...,k}.Let f(v)denote the sum of the color of the vertex v and the colors of all incident edges of v.We say thatφis neighbor sum distinguishing if for each edge uv∈E(G),f(u)=f(v).The smallest number k is called the neighbor sum distinguishing total chromatic number,denoted byχ′′nsd(G).Pil′sniak and Wo′zniak conjectured that for any graph G with at least two vertices,χ′′nsd(G)(G)+3.In this paper,by using the famous Combinatorial Nullstellensatz,we show thatχ′′nsd(G)2(G)+col(G)-1,where col(G)is the coloring number of G.Moreover,we prove this assertion in its list version.     

List neighbor sum distinguishing edge coloring of subcubic graphs

A proper $k$-edge-coloring of a graph with colors in $\{1,2,\dots ,k\}$ 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 $6$ vertices has an NSD edge coloring with at most $\Delta +2$ colors. Huo et al. proved that every subcubic graph without isolated edges has an NSD $6$-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 $6$-edge-coloring result to its list version and show that every subcubic graph without isolated edges has a list NSD $6$-edge-coloring.     

On possible counterexamples to Negami's planar cover conjecture

A simple graph H is a cover of a graph G if there exists a mapping φ from H onto G such that φ maps the neighbors of every vertex υ in H bijectively to the neighbors of φ (υ) in G . Negami conjectured in 1986 that a connected graph has a finite planar cover if and only if it embeds in the projective plane. The conjecture is still open. It follows from the results of Archdeacon, Fellows, Negami, and the first author that the conjecture holds as long as the graph K _1,2,2,2 has no finite planar cover. However, those results seem to say little about counterexamples if the conjecture was not true. We show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. Moreover, we exhibit a finite list of sets of graphs such that the set of excluded minors for the property of having finite planar cover is one of the sets in our list. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 183–206, 2004     

A Planar linear arboricity conjecture

The linear arboricity la(G) of a graph G is the minimum number of linear forests (graphs where every connected component is a path) that partition the edges of G. In 1984, Akiyama et al. [Math Slovaca 30 (1980), 405–417] stated the Linear Arboricity Conjecture (LAC) that the linear arboricity of any simple graph of maximum degree Δ is either ?Δ/2? or ?(Δ + 1)/2?. In [J. L. Wu, J Graph Theory 31 (1999), 129–134; J. L. Wu and Y. W. Wu, J Graph Theory 58(3) (2008), 210–220], it was proven that LAC holds for all planar graphs. LAC implies that for Δ odd, la(G) = ?Δ/2?. We conjecture that for planar graphs, this equality is true also for any even Δ?6. In this article we show that it is true for any even Δ?10, leaving open only the cases Δ = 6, 8. We present also an O(n logn) algorithm for partitioning a planar graph into max{la(G), 5} linear forests, which is optimal when Δ?9. © 2010 Wiley Periodicals, Inc. J Graph Theory     

2-List-coloring planar graphs without monochromatic triangles

We prove that, for every list-assignment of two colors to every vertex of any planar graph, there is a list-coloring such that there is no monochromatic triangle. This proves and extends a conjecture of B. Mohar and R. ?krekovski and a related conjecture of A. Kündgen and R. Ramamurthi.     

On deletions of largest bonds in graphs

A well-known conjecture of Scott Smith is that any two distinct longest cycles of a k-connected graph must meet in at least k vertices when k≥2. We provide a dual version of this conjecture for two distinct largest bonds in a graph. This dual conjecture is established for k?6.     

Cycle Covers of Planar 2-Edge-Connected Graphs

A graph with n vertices is said to have a small cycle cover provided its edges can be covered with at most (2n ? 1)/3 cycles. Bondy [2] has conjectured that every 2-connected graph has a small cycle cover. In [3] Lai and Lai prove Bondy’s conjecture for plane triangulations. In [1] the author extends this result to all planar 3-connected graphs, by proving that they can be covered by at most (n + 1)/2 cycles. In this paper we show that Bondy’s conjecture holds for all planar 2-connected graphs. We also show that all planar 2-edge-connected graphs can be covered by at most (3n ? 3)/4 cycles and we show an infinite family of graphs for which this bound is attained.     

On acyclic edge coloring of planar graphs without intersecting triangles

Let Δ denote the maximum degree of a graph. Fiam?ík first and then Alon et al. again conjectured that every graph is acyclically edge (Δ+2)-colorable. Even for planar graphs, this conjecture remains open. It is known that every triangle-free planar graph is acyclically edge (Δ+5)-colorable. This paper proves that every planar graph without intersecting triangles is acyclically edge (Δ+4)-colorable.     

On the toughness index of planar graphs

The toughness indexτ(G) of a graph G is defined to be the largest integer t such that for any S ? V(G) with |S| > t, c(G - S) < |S| - t, where c(G - S) denotes the number of components of G - S. In particular, 1-tough graphs are exactly those graphs for which τ(G) ≥ 0. In this paper, it is shown that if G is a planar graph, then τ(G) ≥ 2 if and only if G is 4-connected. This result suggests that there may be a polynomial-time algorithm for determining whether a planar graph is 1-tough, even though the problem for general graphs is NP-hard. The result can be restated as follows: a planar graph is 4-connected if and only if it remains 1-tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4-connected planar graph yields a Hamiltonian graph.     

Neighbor Sum Distinguishing Index of Sparse Graphs

A proper k-edge coloring of a graph G is an assignment of one of k colors to each edge of G such that there are no two edges with the same color incident to a common vertex. Let f(v) denote the sum of colors of the edges incident to v. A k-neighbor sum distinguishing edge coloring of G is a proper k-edge coloring of G such that for each edge uv∈E(G), f(u)≠f(v). By χ'_∑(G), we denote the smallest value k in such a coloring of G. Let mad(G) denote the maximum average degree of a graph G. In this paper, we prove that every normal graph with mad(G) ■ and Δ(G) ≥ 8 admits a(Δ(G) + 2)-neighbor sum distinguishing edge coloring. Our approach is based on the Combinatorial Nullstellensatz and discharging method.     

On Group Choosability of Total Graphs

In this paper, we study the group and list group colorings of total graphs and present group coloring versions of the total and list total colorings conjectures. We establish the group coloring version of the total coloring conjecture for the following classes of graphs: graphs with small maximum degree, two-degenerate graphs, planner graphs with maximum degree at least 11, planner graphs without certain small cycles, outerplanar graphs and near outerplanar graphs with maximum degree at least 4. In addition, the group version of the list total coloring conjecture is established for forests, outerplanar graphs and graphs with maximum degree at most two.     

Choosability of planar graphs

A graph G = G(V, E) with lists L(v), associated with its vertices v V, is called L-list colourable if there is a proper vertex colouring of G in which the colour assigned to a vertex v is chosen from L(v). We say G is k-choosable if there is at least one L-list colouring for every possible list assignment L with L(v) = k v V(G).

Now, let an arbitrary vertex v of G be coloured with an arbitrary colour f of L(v). We investigate whether the colouring of v can be continued to an L-list colouring of the whole graph. G is called free k-choosable if such an L-list colouring exists for every list assignment L (L(v) = k v V(G)), every vertex v and every colour f L(v). We prove the equivalence of the well-known conjecture of Erd s et al. (1979): “Every planar graph is 5-choosable” with the following conjecture: “Every planar graph is free 5-choosable”.     

DP-4-colorability of planar graphs without intersecting 5-cycles

DP-coloring of graphs as a generalization of list coloring was introduced by Dvo?ák and Postle (2018). In this paper, we show that every planar graph without intersecting 5-cycles is DP-4-colorable, which improves the result of Hu and Wu (2017), who proved that every planar graph without intersecting 5-cycles is 4-choosable, and the results of Kim and Ozeki (2018).