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 tha...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.展开更多
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 v...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.展开更多
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 t...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.展开更多
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 relationship betwe...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 relationship between planar graph and almost planar Seifert surface is discussed. Using planar graph, we construct an alternating amphicheiral prime knot with crossing number n for any even number n 〉 4. This gives an affirmative answer to problem 1.66（B） on Kirby＇s problem list .展开更多
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...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.展开更多
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 co...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.展开更多
The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that ...The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that for a 1-planar graph G.展开更多
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...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.展开更多
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...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.展开更多
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 t...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.展开更多
A coloring of graph G is an injective coloring if its restriction to the neighborhood of any vertex is injective, which means that any two vertices get different colors if they have a common neighbor. The injective ch...A coloring of graph G is an injective coloring if its restriction to the neighborhood of any vertex is injective, which means that any two vertices get different colors if they have a common neighbor. The injective chromatic number χi(G) of G is the least integer k such that G has an injective k-coloring. In this paper, we prove that(1) if G is a planar graph with girth g ≥ 6 and maximum degree △ ≥ 7, then χi(G) ≤ △ + 2;(2) if G is a planar graph with △ ≥ 24 and without 3,4,7-cycles, then χi(G) ≤ △ + 2.展开更多
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 ...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.展开更多
Let G = （V, E） be a simple graph. A function f ： E → {＋1,-1} is called a signed cycle domination function （SCDF） of G if ∑e∈E（C） f（e） ≥ 1 for every induced cycle C of G. The signed cycle domination numbe...Let G = （V, E） be a simple graph. A function f ： E → {＋1,-1} is called a signed cycle domination function （SCDF） of G if ∑e∈E（C） f（e） ≥ 1 for every induced cycle C of G. The signed cycle domination number of G is defined as γ′sc（G） = min{∑e∈E f（e）｜ f is an SCDF of G}. This paper will characterize all maxima] planar graphs G with order n ≥ 6 and γ′sc（G） =n.展开更多
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 g...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.展开更多
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...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.展开更多
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...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.展开更多
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 deg...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.展开更多
文摘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.
基金The authors extend their appreciation to the Deanship of Scientific Research at King Khalid University for funding this work through the Large Group Research Project under grant number(R.G.P.2/181/44).
文摘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.
基金Project supporte（t by the National Natural Science Foundation of China （Grant No.10571117）, and the Youth Science Foundation of Shanghai Municipal Commission of Education （Grant No.01QN6262）
文摘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.
文摘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 relationship between planar graph and almost planar Seifert surface is discussed. Using planar graph, we construct an alternating amphicheiral prime knot with crossing number n for any even number n 〉 4. This gives an affirmative answer to problem 1.66（B） on Kirby＇s problem list .
文摘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.
基金Supported by the Natural Science Research Project of Ordinary Universities in Jiangsu(08KJB110002)Supported by the Program for ETHYTC(08QNZCK03)Supported by the NSFC(10671095)
文摘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.
文摘The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that for a 1-planar graph G.
基金Supported in part by the Natural Science Basic Research Program of Shaanxi(Nos.2023-JC-YB-001,2023-JC-YB-054)the Fundamental Research Funds for the Central Universities(No.ZYTS24076)the National Natural Science Foundation of China(No.11871055)。
文摘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.
基金supported by the National Natural Science Foundation of China (No.12271438, No.12071370 and U1803263)the Science Found of Qinhai Province (No.2022-ZJ-753)+2 种基金Shaanxi Fundamental Science Research Project for Mathematics and Physics (No.22JSZ009)Shangluo University Doctoral Initiation Fund Project(No.22SKY112)Shangluo University Key Disciplines Project (Discipline name:Mathematics)。
文摘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.
基金partially supported by the National Natural Science Foundation of China(Grant No.11971196)Hubei Provincial Science and Technology Innovation Base(Platform)Special Project 2020DFH002+1 种基金the second author was partially supported by the National Natural Science Foundation of China(Grant Nos.11901318,12131013)the Young Elite Scientists Sponsorship Program by Tianjin(Grant No.TJSQNTJ-2020-09)。
文摘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.
基金supported by the National Natural Science Foundation of China (No.11871377)。
文摘A coloring of graph G is an injective coloring if its restriction to the neighborhood of any vertex is injective, which means that any two vertices get different colors if they have a common neighbor. The injective chromatic number χi(G) of G is the least integer k such that G has an injective k-coloring. In this paper, we prove that(1) if G is a planar graph with girth g ≥ 6 and maximum degree △ ≥ 7, then χi(G) ≤ △ + 2;(2) if G is a planar graph with △ ≥ 24 and without 3,4,7-cycles, then χi(G) ≤ △ + 2.
基金the National Natural Science Foundation of China(Nos.11922112 and 11771221)the Natural Science Foundation of Tianjin(Nos.20JCZDJC00840 and 20JCJQJC00090)+2 种基金Yong-Xin Lan was partially supported by the National Natural Science Foundation of China(No.12001154)the Natural Science Foundation of Hebei Province(No.A2021202025)the Special Funds for Jointly Building Universities of Tianjin(No.280000307).
文摘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.
基金Supported by Doctoral Scientific Research Fund of Harbin Normal University(Grant No.KGB201008)
文摘Let G = （V, E） be a simple graph. A function f ： E → {＋1,-1} is called a signed cycle domination function （SCDF） of G if ∑e∈E（C） f（e） ≥ 1 for every induced cycle C of G. The signed cycle domination number of G is defined as γ′sc（G） = min{∑e∈E f（e）｜ f is an SCDF of G}. This paper will characterize all maxima] planar graphs G with order n ≥ 6 and γ′sc（G） =n.
基金the National Natural Science Foundationof China (No.196 710 5 0 )
文摘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.
基金supported by National Natural Science Foundation of China (Grant No. 10871119)NaturalScience Foundation of Shandong Province (Grant No. Y2008A20).
文摘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.
基金This work was partially supported by the National Natural Science Foundation of China (Grant No. 10471131)
文摘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.
基金supported by Natural Science Foundation of Shandong Province (Grant No. ZR2009AM009)Scientific Research Foundation for the Excellent Middle-Aged and Youth Scientists of Shandong Province (Grant No. BS2012SF016)National Natural Science Foundation of China (Grant Nos.11001055 and 11101243)
文摘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.
