On the (Δ + 2)-Total-Colorability of Planar Graphs with 7-Cycles Containing at Most Two Chords

The Total Coloring Conjecture (TCC) proposes that every simple graph G is (Δ + 2)-totally-colorable, where Δ is the maximum degree of G. For planar graph, TCC is open only in case Δ = 6. In this paper, we prove that TCC holds for planar graph with Δ = 6 and every 7-cycle contains at most two chords.

Pythagorean Neutrosophic Planar Graphs with an Application in Decision-Making

Graph theory has a significant impact and is crucial in the structure of many real-life situations.To simulate uncertainty and ambiguity,many extensions of graph theoretical notions were created.Planar graphs play a vital role in modelling which has the property of non-crossing edges.Although crossing edges benefit,they have some drawbacks,which paved the way for the introduction of planar graphs.The overall purpose of the study is to contribute to the conceptual development of the Pythagorean Neutrosophic graph.The basic methodology of our research is the incorporation of the analogous concepts of planar graphs in the Pythagorean Neutrosophic graphs.The significant finding of our research is the introduction of Pythagorean Neutrosophic Planar graphs,a conceptual blending of Pythagorean Neutro-sophic and Planar graphs.The idea of Pythagorean Neutrosophic multigraphs and dual graphs are also introduced to deal with the ambiguous situations.This paper investigates the Pythagorean Neutrosophic planar values,which form the edges of the Pythagorean neutrosophic graphs.The concept of Pythagorean Neutrosophic dual graphs,isomorphism,co-weak and weak isomorphism have also been explored for Pythagorean Neutrosophic planar graphs.A decision-making algorithm was proposed with a numerical illustra-tion by using the Pythagorean Neutrosophic fuzzy graph.

Power domination in planar graphs with small diameter

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known vertex covering and dominating set problems in graph theory. In this paper, it was shown that the power domination number of an outerplanar graph with the diameter two or a 2-connected outerplanar graph with the diameter three is precisely one. Upper bounds on the power domination number for a general planar graph with the diameter two or three were determined as an immediate consequences of results proven by Dorfling, et al. Also, an infinite family of outerplanar graphs with the diameter four having arbitrarily large power domination numbers were given.

A NOTE ON STRONG EMBEDDINGS OF MAXIMAL PLANAR GRAPHS ON NON ORIENTABLE SURFACES

In this paper, it is shown that for every maximal planar graph G=(V,E) , a strong embedding on some non orientable surface with genus at most |V(G)|-22 is admitted such that the surface dual of G is also a planar graph. As a corollary, an interpolation theorem for strong embeddings of G on non orientable surfaces is obtained.

Improper Choosability of Planar Graphs without 6-circuits

A graph G is called（k,d）＊-choosable if for every list assignment L satisfying ｜L（v）｜=k for all v ∈ V（G）,there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself.In this paper,it is shown that every planar graph without 6-circuits and a triangle adjacent to itself or a quadrangle is（3,1）＊-choosable.

Neighbor Sum Distinguishing Total Choosability of Planar Graphs with Maximum Degree at Least 10

A neighbor sum distinguishing(NSD)total coloringφof G is a proper total coloring of G such thatΣz∈EG(u)U{u}φ(z)≠Σz∈EG(v)U{v}φ(z)for each edge uv∈E(G),where EG(u)is the set of edges incident with a vertex u.In 2015,Pilśniak and Wozniak conjectured that every graph with maximum degreeΔhas an NSD total(Δ+3)-coloring.Recently,Yang et al.proved that the conjecture holds for planar graphs withΔ≥10,and Qu et al.proved that the list version of the conjecture also holds for planar graphs withΔ≥13.In this paper,we improve their results and prove that the list version of the conjecture holds for planar graphs withΔ≥10.

Incidence Coloring of Outer-1-planar Graphs

A graph is outer-1-planar if it can be drawn in the plane so that all vertices lie on the outer-face and each edge crosses at most one another edge.It is known that every outer-1-planar graph is a planar partial3-tree.In this paper,we conjecture that every planar graph G has a proper incidence(Δ(G)+2)-coloring and confirm it for outer-1-planar graphs with maximum degree at least 8 or with girth at least 4.Specifically,we prove that every outer-1-planar graph G has an incidence(Δ(G)+3,2)-coloring,and every outer-1-planar graph G with maximum degree at least 8 or with girth at least 4 has an incidence(Δ(G)+2,2)-coloring.

Fractional Coloring Planar Graphs under Steinberg-type Conditions

A Steinberg-type conjecture on circular coloring is recently proposed that for any prime p≥5,every planar graph of girth p without cycles of length from p+1 to p(p-2)is Cp-colorable(that is,it admits a homomorphism to the odd cycle Cp).The assumption of p≥5 being prime number is necessary,and this conjecture implies a special case of Jaeger’s Conjecture that every planar graph of girth 2p-2 is Cp-colorable for prime p≥5.In this paper,combining our previous results,we show the fractional coloring version of this conjecture is true.Particularly,the p=5 case of our fractional coloring result shows that every planar graph of girth 5 without cycles of length from 6 to 15 admits a homomorphism to the Petersen graph.

Extremal P_(8)-Free/P_(9)-Free Planar Graphs

An H-free graph is a graph not containing the given graph H as a subgraph.It is well known that the Turán number ex(n,H)is the maximum number of edges in an H-free graph on n vertices.Based on this definition,we define ex_(P)(n,H)to restrict the graph classes to planar graphs,that is,ex_(P)(n,H)=max{|E(G)|:G∈G,where G is a family of all H-free planar graphs on n vertices.Obviously,we have ex_(P)(n,H)=3n−6 if the graph H is not a planar graph.The study is initiated by Dowden(J Graph Theory 83:213–230,2016),who obtained some results when H is considered as C_(4)or C_(5).In this paper,we determine the values of ex_(P)(n,Pk)with k∈{8,9},where Pk is a path with k vertices.

Spectral Radius of Hamiltonian Planar Graphs and Outerplanar Graphs

The spectral radius is an important parameter of a graph related to networks. A method for estimating the spectral radius of each spanning subgraph is used to prove that the spectral radius of a Hamiltonian planar graph of order n≥4 is less than or equal to 2+3n-11 and the spectral radius of the outerplanar graph of order n≥6 is less than or equal to 22+n-5, which are improvements over previous results. A direction for further study is then suggested.

Combinatorial Invariants on Planar Graphs

This paper introduces three kinds of operators on planar graphs with binary weights on edges, for which combinatorial invariants on two kinds of equivalences are found. Further, it is shown that the Jones polynomial and the bracket polynomial which are proved to be new topological invariants on knots in topology become special cases. Moreover, these invariants are a kind of generalization of Tutte polynomial on graphs.

Neighbor Sum Distinguishing Total Choice Number of Planar Graphs without 6-cycles

Pilsniak and Wozniak put forward the concept of neighbor sum distinguishing(NSD)total coloring and conjectured that any graph with maximum degreeΔadmits an NSD total(Δ+3)-coloring in 2015.In 2016,Qu et al.showed that the list version of the conjecture holds for any planar graph withΔ≥13.In this paper,we prove that any planar graph withΔ≥7 but without 6-cycles satisfies the list version of the conjecture.

Group Edge Choosability of Planar Graphs without Adjacent Short Cycles

In this paper, we prove that 2-degenerate graphs and some planar graphs without adjacent short cycles are group （△ （G）＋1）-edge-choosable, and some planar graphs with large girth and maximum degree are group △（G）-edge-choosable.

Some Planar Graphs with Star Chromatic Number Between Three and Four

We construct sonic infinite family of planar graphs with star chromatic number, where, partially answering a question of Vince，

A survey on book-embedding of planar graphs

The book-embedding problem arises in several area,such as very large scale integration(VLSI)design and routing multilayer printed circuit boards(PCBs).It can be used into various practical application fields.A book embedding of a graph G is an embedding of its vertices along the spine of a book,and an embedding of its edges to the pages such that edges embedded on the same page do not intersect.The minimum number of pages in which a graph G can be embedded is called the pagenumber or book-thickness of the graph G.It is an important measure of the quality for book-embedding.It is NP-hard to research the pagenumber of book-embedding for a graph G.This paper summarizes the studies on the book-embedding of planar graphs in recent years.

Gromov Hyperbolicity of Periodic Planar Graphs

The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it.The main result in this paper is a very simple characterization of the hyperbolicity of a large class of periodic planar graphs.

Acyclic edge colorings of planar graphs and series-parallel graphs

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. For planar graphs G with girth g(G), we prove that a (G) max{2Δ(G) + 2, Δ(G) + 22} if g(G) 3, a (G) Δ(G) + 2 if g(G) 5, a (G) Δ(G) + 1 if g(G) 7, and a (G) = Δ(G) if g(G) 16 and Δ(G) 3. For series-parallel graphs G, we have a (G) Δ(G) + 1.

Total colorings of planar graphs with maximum degree at least 8

Planar graphs with maximum degree Δ 8 and without 5- or 6-cycles with chords are proved to be (Δ + 1)-totally-colorable.

On total chromatic number of planar graphs without 4-cycles

Let G be a simple graph with maximum degree Δ(G) and total chromatic number x ve (G). Vizing conjectured that Δ(G) + 1 ? X ve (G) ? δ(G) + 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs is Δ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then x ve (G) ? 8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.

Planar graphs with maximum degree 8 and without intersecting chordal 4-cycles are 9-totally colorable

The minimum number of colors needed to properly color the vertices and edges of a graph G is called the total chromatic number of G and denoted by χ'' (G). It is shown that if a planar graph G has maximum degree Δ≥9, then χ'' (G) = Δ + 1. In this paper, we prove that if G is a planar graph with maximum degree 8 and without intersecting chordal 4-cycles, then χ ''(G) = 9.