Displaying similar documents to “Edge-coloring of a family of regular graphs.”

M 2 -Edge Colorings Of Cacti And Graph Joins

Július Czap, Peter Šugerek, Jaroslav Ivančo (2016)

Discussiones Mathematicae Graph Theory

Similarity:

An edge coloring φ of a graph G is called an M2-edge coloring if |φ(v)| ≤ 2 for every vertex v of G, where φ(v) is the set of colors of edges incident with v. Let 𝒦2(G) denote the maximum number of colors used in an M2-edge coloring of G. In this paper we determine 𝒦2(G) for trees, cacti, complete multipartite graphs and graph joins.

Decompositions of Plane Graphs Under Parity Constrains Given by Faces

Július Czap, Zsolt Tuza (2013)

Discussiones Mathematicae Graph Theory

Similarity:

An edge coloring of a plane graph G is facially proper if no two faceadjacent edges of G receive the same color. A facial (facially proper) parity edge coloring of a plane graph G is an (facially proper) edge coloring with the property that, for each color c and each face f of G, either an odd number of edges incident with f is colored with c, or color c does not occur on the edges of f. In this paper we deal with the following question: For which integers k does there exist a facial...

Interval Edge-Colorings of Cartesian Products of Graphs I

Petros A. Petrosyan, Hrant H. Khachatrian, Hovhannes G. Tananyan (2013)

Discussiones Mathematicae Graph Theory

Similarity:

A proper edge-coloring of a graph G with colors 1, . . . , t is an interval t-coloring if all colors are used and the colors of edges incident to each vertex of G form an interval of integers. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. Let [...] be the set of all interval colorable graphs. For a graph G ∈ [...] , the least and the greatest values of t for which G has an interval t-coloring are denoted by w(G) and W(G), respectively....

Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six

Yuehua Bu, Ko-Wei Lih, Weifan Wang (2011)

Discussiones Mathematicae Graph Theory

Similarity:

An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge-coloring o G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring of G is denoted by χ'ₐ(G). We prove that χ'ₐ(G) is at most the maximum degree plus 2 if G is a planar graph without isolated edges whose girth is at least 6. This gives new evidence to a conjecture proposed in [Z. Zhang, L. Liu,...

Sum List Edge Colorings of Graphs

Arnfried Kemnitz, Massimiliano Marangio, Margit Voigt (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a simple graph and for every edge e ∈ E let L(e) be a set (list) of available colors. The graph G is called L-edge colorable if there is a proper edge coloring c of G with c(e) ∈ L(e) for all e ∈ E. A function f : E → ℕ is called an edge choice function of G and G is said to be f-edge choosable if G is L-edge colorable for every list assignment L with |L(e)| = f(e) for all e ∈ E. Set size(f) = ∑e∈E f(e) and define the sum choice index χ′sc(G) as the minimum of size(f)...

On Twin Edge Colorings of Graphs

Eric Andrews, Laars Helenius, Daniel Johnston, Jonathon VerWys, Ping Zhang (2014)

Discussiones Mathematicae Graph Theory

Similarity:

A twin edge k-coloring of a graph G is a proper edge coloring of G with the elements of Zk so that the induced vertex coloring in which the color of a vertex v in G is the sum (in Zk) of the colors of the edges incident with v is a proper vertex coloring. The minimum k for which G has a twin edge k-coloring is called the twin chromatic index of G. Among the results presented are formulas for the twin chromatic index of each complete graph and each complete bipartite graph