An edge coloring of hypergraph H is a function such that holds for any pair of intersecting edges . The minimum number of colors in edge colorings of H is called the chromatic index of H and is ...An edge coloring of hypergraph H is a function such that holds for any pair of intersecting edges . The minimum number of colors in edge colorings of H is called the chromatic index of H and is denoted by . Erdös, Faber and Lovász proposed a famous conjecture that holds for any loopless linear hypergraph H with n vertices. In this paper, we show that is true for gap-restricted hypergraphs. Our result extends a result of Alesandroni in 2021.展开更多
Graph colouring is the system of assigning a colour to each vertex of a graph.It is done in such a way that adjacent vertices do not have equal colour.It is fundamental in graph theory.It is often used to solve real-w...Graph colouring is the system of assigning a colour to each vertex of a graph.It is done in such a way that adjacent vertices do not have equal colour.It is fundamental in graph theory.It is often used to solve real-world problems like traffic light signalling,map colouring,scheduling,etc.Nowadays,social networks are prevalent systems in our life.Here,the users are considered as vertices,and their connections/interactions are taken as edges.Some users follow other popular users’profiles in these networks,and some don’t,but those non-followers are connected directly to the popular profiles.That means,along with traditional relationship(information flowing),there is another relation among them.It depends on the domination of the relationship between the nodes.This type of situation can be modelled as a directed fuzzy graph.In the colouring of fuzzy graph theory,edge membership plays a vital role.Edge membership is a representation of flowing information between end nodes of the edge.Apart from the communication relationship,there may be some other factors like domination in relation.This influence of power is captured here.In this article,the colouring of directed fuzzy graphs is defined based on the influence of relationship.Along with this,the chromatic number and strong chromatic number are provided,and related properties are investigated.An application regarding COVID-19 infection is presented using the colouring of directed fuzzy graphs.展开更多
An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ'α(G) of G is the smallest k such that G has an acyclic edge coloring u...An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ'α(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.It was conjectured that every simple graph G with maximum degree Δ has χ'_α(G) ≤Δ+2.A1-planar graph is a graph that can be drawn in the plane so that each edge is crossed by at most one other edge.In this paper,we show that every 1-planar graph G without 4-cycles has χ'_α(G)≤Δ+22.展开更多
A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by X＇a（G）, is the least number of colors such that G has an acyclic edge coloring. A gra...A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by X＇a（G）, is the least number of colors such that G has an acyclic edge coloring. 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 X＇a（G） ≤△ A（G）＋ 22, if G is a triangle-free 1-planar graph.展开更多
A strong k-edge-coloring of a graph G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex, or being adjacent to the same edge of G, axe assigned different colors....A strong k-edge-coloring of a graph G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex, or being adjacent to the same edge of G, axe assigned different colors. The strong chromatic index of G is the smallest integer k for which G has a strong k-edge-coloring. In this paper, we have shown that the strong chromatic index is no larger than 6 for outerplanax graphs with maximum degree 3.展开更多
Let G be a graph embeddable in a surface of nonnegative characteristic with maximum degree six. In this paper, we prove that if G contains no a vertex v which is contained in all cycles of lengths from 3 to 6, then G ...Let G be a graph embeddable in a surface of nonnegative characteristic with maximum degree six. In this paper, we prove that if G contains no a vertex v which is contained in all cycles of lengths from 3 to 6, then G is of Class 1.展开更多
A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G.The acyclic chromatic index of G is the least number of colors such that G has an acyclic edge coloring and denoted byχ′a(G).An IC-p...A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G.The acyclic chromatic index of G is the least number of colors such that G has an acyclic edge coloring and denoted byχ′a(G).An IC-plane graph is a topological graph where every edge is crossed at most once and no two crossed edges share a vertex.In this paper,it is proved thatχ′a(G)≤Δ(G)+10,if G is an IC-planar graph without adjacent triangles andχ′a(G)≤Δ(G)+8,if G is a triangle-free IC-planar graph.展开更多
In this paper, the authors have obtained some lower bounds on the size of a 7-critical graph,and some results about the planar graph conjecture have been given.
文摘An edge coloring of hypergraph H is a function such that holds for any pair of intersecting edges . The minimum number of colors in edge colorings of H is called the chromatic index of H and is denoted by . Erdös, Faber and Lovász proposed a famous conjecture that holds for any loopless linear hypergraph H with n vertices. In this paper, we show that is true for gap-restricted hypergraphs. Our result extends a result of Alesandroni in 2021.
基金supported and funded by the Basic Science Research Program through the National Research Foundation of Korea(NRF)funded by the Ministry of Education(2018R1D1A1B07049321).
文摘Graph colouring is the system of assigning a colour to each vertex of a graph.It is done in such a way that adjacent vertices do not have equal colour.It is fundamental in graph theory.It is often used to solve real-world problems like traffic light signalling,map colouring,scheduling,etc.Nowadays,social networks are prevalent systems in our life.Here,the users are considered as vertices,and their connections/interactions are taken as edges.Some users follow other popular users’profiles in these networks,and some don’t,but those non-followers are connected directly to the popular profiles.That means,along with traditional relationship(information flowing),there is another relation among them.It depends on the domination of the relationship between the nodes.This type of situation can be modelled as a directed fuzzy graph.In the colouring of fuzzy graph theory,edge membership plays a vital role.Edge membership is a representation of flowing information between end nodes of the edge.Apart from the communication relationship,there may be some other factors like domination in relation.This influence of power is captured here.In this article,the colouring of directed fuzzy graphs is defined based on the influence of relationship.Along with this,the chromatic number and strong chromatic number are provided,and related properties are investigated.An application regarding COVID-19 infection is presented using the colouring of directed fuzzy graphs.
基金Research supported by the National Natural Science Foundation of China (No.12031018)Research supported by the National Natural Science Foundation of China (No.12071048)+3 种基金Research supported by the National Natural Science Foundation of China(No.12071351)Science and Technology Commission of Shanghai Municipality (No.18dz2271000)Doctoral Scientific Research Foundation of Weifang University (No.2021BS01)Natural Science Foundation of Shandong Province (No.ZR2022MA060)。
文摘An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles in G.The acyclic chromatic index χ'α(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.It was conjectured that every simple graph G with maximum degree Δ has χ'_α(G) ≤Δ+2.A1-planar graph is a graph that can be drawn in the plane so that each edge is crossed by at most one other edge.In this paper,we show that every 1-planar graph G without 4-cycles has χ'_α(G)≤Δ+22.
基金Supported by National Natural Science Foundation of China(Grant No.11271365)
文摘A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by X＇a（G）, is the least number of colors such that G has an acyclic edge coloring. 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 X＇a（G） ≤△ A（G）＋ 22, if G is a triangle-free 1-planar graph.
基金Supported by the National Natural Science Foundation of China under Grant No.11501050the Fundamental Research Funds for the Central Universities under Grant No.310812151003
文摘A strong k-edge-coloring of a graph G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex, or being adjacent to the same edge of G, axe assigned different colors. The strong chromatic index of G is the smallest integer k for which G has a strong k-edge-coloring. In this paper, we have shown that the strong chromatic index is no larger than 6 for outerplanax graphs with maximum degree 3.
基金Supported by the National Natural Science Foundation of China(No.11671053)
文摘Let G be a graph embeddable in a surface of nonnegative characteristic with maximum degree six. In this paper, we prove that if G contains no a vertex v which is contained in all cycles of lengths from 3 to 6, then G is of Class 1.
基金supported by the National Natural Science Foundation of China (No. 11771443)Natural Science Foundation of Shandong Province (No. ZR2019BA016)+1 种基金by the foundation of innovative Science and technology for youth in universities of Shandong Province (No. 2019KJI001)under the financial support from the Zaozhaung University Research Fund Project in 2019
文摘A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G.The acyclic chromatic index of G is the least number of colors such that G has an acyclic edge coloring and denoted byχ′a(G).An IC-plane graph is a topological graph where every edge is crossed at most once and no two crossed edges share a vertex.In this paper,it is proved thatχ′a(G)≤Δ(G)+10,if G is an IC-planar graph without adjacent triangles andχ′a(G)≤Δ(G)+8,if G is a triangle-free IC-planar graph.
文摘In this paper, the authors have obtained some lower bounds on the size of a 7-critical graph,and some results about the planar graph conjecture have been given.
