A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each ...
详细信息
A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)| >= min{5, triangle + 1} for each vertex v and |L(e)| >= max{5, d(v) + 1, d(w) + 1} for each edge e = vw, where triangle is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with triangle + 1 colors if triangle >= 4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition. (C) 2004 Elsevier B. V. All rights reserved.
Let c(n) be themaximum number of cycles in an outerplanar graph with n vertices. We show that lim c(n)(1/n) exists and equals beta = 1.502837 ..., where beta is a constant related to the recurrence x(n+1) = 1 + x(n)(2...
详细信息
Let c(n) be themaximum number of cycles in an outerplanar graph with n vertices. We show that lim c(n)(1/n) exists and equals beta = 1.502837 ..., where beta is a constant related to the recurrence x(n+1) = 1 + x(n)(2), x(0) = 1. The same result holds for the larger class of series-parallel graphs.
The st-bond polytope of a graph is the convex hull of the incidence vectors of its st-bonds, where an st-bond is a minimal st-cut. In this paper, we provide a linear description of the st-bond polytope on series-paral...
详细信息
The st-bond polytope of a graph is the convex hull of the incidence vectors of its st-bonds, where an st-bond is a minimal st-cut. In this paper, we provide a linear description of the st-bond polytope on series-parallel graphs. We also show that the st-bond polytope is the intersection of the st-cut dominant and the bond polytope.
In this paper, we consider the weighted perfect domination problem in series-parallel graphs. Suppose G = (V, E) is a graph in which every vertex x is-an-element-of V has a cost c(x) and every edge e is-an-element-of ...
详细信息
In this paper, we consider the weighted perfect domination problem in series-parallel graphs. Suppose G = (V, E) is a graph in which every vertex x is-an-element-of V has a cost c(x) and every edge e is-an-element-of E has a cost c(e). The weighted perfect domination problem is to find a subset D subset-of V such that every vertex not in D is adjacent to exactly one vertex in D and its total cost c(D) = SIGMA{c(x): x is-an-element-of D} + SIGMA{c(x, y): x is-not-an-element-of D, y is-an-element-of D and (x, y) is-an-element-of E} is minimum. This problem is NP-complete for bipartite graphs and chordal graphs. In this paper, we present a linear time algorithm for the problem in series-parallel graphs.
We give a simple polynomial-time algorithm to exactly count the number of Euler tours (ETs) of any Eulerian generalized series-parallel graph, and show how to adapt this algorithm to exactly sample a random ET of the ...
详细信息
We give a simple polynomial-time algorithm to exactly count the number of Euler tours (ETs) of any Eulerian generalized series-parallel graph, and show how to adapt this algorithm to exactly sample a random ET of the given generalized series-parallel graph. Note that the class of generalized series-parallel graphs includes all outerplanar graphs. We can perform the counting in time O (m Delta(3)), where Delta is the maximum degree of the graph with m edges. We use O (mn Delta(2) log Delta) bits to store intermediate values during our computations. To date, these are the first known polynomial-time algorithms to count or sample ETs of any class of graphs;there are no other known polynomial-time algorithms to even approximately count or sample ETs of any other class of graphs. The problem of counting ETs is known to be # P-complete for general graphs (Brightwell and Winkler, 2005 [2]) also for planar graphs (Creed, 2010 [3]). (C) 2011 Elsevier B.V. All rights reserved.
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.
The total chromatic number of series-parallel graphs of maximum degree greater than or equal to 4 will be determined using the double inductions and the method of exchanging colors from the aspect of configuration pro...
详细信息
The total chromatic number of series-parallel graphs of maximum degree greater than or equal to 4 will be determined using the double inductions and the method of exchanging colors from the aspect of configuration property. Thus, the result of paper [7] is a special case of this paper.
A feedback vertex set is a subset of vertices in a graph, whose deletion from the graph makes the resulting graph acyclic. In this paper, we study the minimum-weight feedback vertex set problem in series-parallel grap...
详细信息
A feedback vertex set is a subset of vertices in a graph, whose deletion from the graph makes the resulting graph acyclic. In this paper, we study the minimum-weight feedback vertex set problem in series-parallel graphs and present a linear-time exact algorithm to solve it.
Let G be a graph, and let each vertex v of G have a positive integer weight omega(v). A multicoloring of G is to assign each vertex v a set of omega(v) colors so that any pair of adjacent vertices receive disjoint set...
详细信息
Let G be a graph, and let each vertex v of G have a positive integer weight omega(v). A multicoloring of G is to assign each vertex v a set of omega(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. This paper presents an algorithm to find a multicoloring of a given series-parallel graph G with the minimum number of colors in time 0(nW), where n is the number of vertices and W is the maximum weight of vertices in G.
暂无评论