Let G be a simple graph with vertex set V(G) and edge set E(G). An edge coloring C of G is called an edge cover coloring, if each color appears at least once at each vertex . The maximum positive integer k such that G...Let G be a simple graph with vertex set V(G) and edge set E(G). An edge coloring C of G is called an edge cover coloring, if each color appears at least once at each vertex . The maximum positive integer k such that G has a k edge cover coloring is called the edge cover chromatic number of G and is denoted by . It is known that for any graph G, . If , then G is called a graph of CI class, otherwise G is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification on double graph of some graphs and a polynomial time algorithm can be obtained for actually finding such a classification by our proof.展开更多
Let G be a multigraph with vertex set V（G）. Assume that a positive integer f（v） with 1 ≤ f（v） ≤ d（v） is associated with each vertex v ∈ V. An edge coloring of G is called an f-edge cover-coloring, if each c...Let G be a multigraph with vertex set V（G）. Assume that a positive integer f（v） with 1 ≤ f（v） ≤ d（v） is associated with each vertex v ∈ V. An edge coloring of G is called an f-edge cover-coloring, if each color appears at each vertex v at least f（v） times. Let X＇fc（G） be the maximum positive integer k for which an f-edge cover-coloring with k colors of G exists. In this paper, we give a new lower bound of X＇fc（G）, which is sharp.展开更多
文摘Let G be a simple graph with vertex set V(G) and edge set E(G). An edge coloring C of G is called an edge cover coloring, if each color appears at least once at each vertex . The maximum positive integer k such that G has a k edge cover coloring is called the edge cover chromatic number of G and is denoted by . It is known that for any graph G, . If , then G is called a graph of CI class, otherwise G is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification on double graph of some graphs and a polynomial time algorithm can be obtained for actually finding such a classification by our proof.
文摘Let G be a multigraph with vertex set V（G）. Assume that a positive integer f（v） with 1 ≤ f（v） ≤ d（v） is associated with each vertex v ∈ V. An edge coloring of G is called an f-edge cover-coloring, if each color appears at each vertex v at least f（v） times. Let X＇fc（G） be the maximum positive integer k for which an f-edge cover-coloring with k colors of G exists. In this paper, we give a new lower bound of X＇fc（G）, which is sharp.
