We prove that every planar graph is contained in H1 (R) H2 (R) K2 for some graphs H1 and H2 both with treewidth 2. This resolves a question of Liu, Norin and Wood [arXiv:2410.20333]. We also show this result is best p...
详细信息
We prove that every planar graph is contained in H1 (R) H2 (R) K2 for some graphs H1 and H2 both with treewidth 2. This resolves a question of Liu, Norin and Wood [arXiv:2410.20333]. We also show this result is best possible in the following sense: for any c is an element of N, there is a planar graph G such that for any tree T and graph H with tw(H) <= 2, G is not contained in H (R) T (R) Kc.
It is well known that every planar graph G is 2-colorable in such a way that no 3-cycle of G is monochromatic. In this paper, we prove that G has a 2-coloring such that no cycle of length 3 or 4 is monochromatic. The ...
详细信息
It is well known that every planar graph G is 2-colorable in such a way that no 3-cycle of G is monochromatic. In this paper, we prove that G has a 2-coloring such that no cycle of length 3 or 4 is monochromatic. The complete graph K-5 does not admit such a coloring. On the other hand, we extend the result to K-5-minor-free graphs. There Eire planar graphs with the property that each of their 2-colorings has a monochromatic cycle of length 3, 4, or 5. In this sense, our result is best possible. (C) 2004 Wiley Periodicals, Inc.
We consider the problem of coloring a planar graph with the minimum number of colors so that each color class avoids one or more forbidden graphs as subgraphs. We perform a detailed study of the computational complexi...
详细信息
We consider the problem of coloring a planar graph with the minimum number of colors so that each color class avoids one or more forbidden graphs as subgraphs. We perform a detailed study of the computational complexity of this problem. We present a complete picture for the case with a single forbidden connected (induced or noninduced) subgraph. The 2-coloring problem is NP-hard if the forbidden subgraph is a tree with at least two edges, and it is polynomially solvable in all other cases. The 3-coloring problem is NP-hard if the forbidden subgraph is a path with at least one edge, and it is polynomially solvable in all other cases. We also derive results for several forbidden sets of cycles. In particular, we prove that it is NP-complete to decide if a planar graph can be 2-colored so that no cycle of length at most 5 is monochromatic.
For each constant k, we present a linear time algorithm that, given a planar graph G, either finds a minimum odd cycle vertex transversal in G or guarantees that there is no transversal of size at most k. (C) 2007 Els...
详细信息
For each constant k, we present a linear time algorithm that, given a planar graph G, either finds a minimum odd cycle vertex transversal in G or guarantees that there is no transversal of size at most k. (C) 2007 Elsevier B.V. All rights reserved.
Let G be any connected graph on n vertices, n >= 2. Let k be any positive integer. Suppose that a fire breaks out at some vertex of G. Then, in each turn k firefighters can protect vertices of G - each can protect ...
详细信息
Let G be any connected graph on n vertices, n >= 2. Let k be any positive integer. Suppose that a fire breaks out at some vertex of G. Then, in each turn k firefighters can protect vertices of G - each can protect one vertex not yet on fire;Next the fire spreads to all unprotected neighbours. The k-surviving rate of G, denoted by rho(k)(G), is the expected fraction of vertices that can be saved from the fire by k firefighters, provided that the starting vertex is chosen uniformly at random. In this paper, it is shown that for any planar graph G we have rho(3)(G) >= 2/21 Moreover, 3 firefighters are needed for the first step only;after that it is enough to have 2 firefighters per each round. This result significantly improves the known solutions to a problem by Cai and Wang (there was no positive bound known for the surviving rate of general planar graph with only 3 firefighters). The proof is done using the separator theorem for planar graphs. (C) 2015 Elsevier B.V. All rights reserved.
Consider an n-vertex planar graph G. The depth of an embedding Gamma of G is the maximum distance of its internal faces from the external one. Several researchers pointed out that the quality of a planar embedding can...
详细信息
Consider an n-vertex planar graph G. The depth of an embedding Gamma of G is the maximum distance of its internal faces from the external one. Several researchers pointed out that the quality of a planar embedding can be measured in terms of its depth. We present an O(n (4))-time algorithm for computing an embedding of G with minimum depth. This bound improves on the best previous bound by an O(nlog n) factor. As a side effect, our algorithm improves the bounds of several algorithms that require the computation of a minimum-depth embedding.
We give an O(n log n) algorithm for computing the girth (shortest cycle) of an undirected n-vertex planar graph. Our solution extends to any graph of bounded genus. This improves upon the best previously known algorit...
详细信息
We give an O(n log n) algorithm for computing the girth (shortest cycle) of an undirected n-vertex planar graph. Our solution extends to any graph of bounded genus. This improves upon the best previously known algorithms for this problem.
The multiplicity of the second-largest eigenvalue of the adjacency matrix A ( G ) of a connected graph G, denoted by m ( lambda 2 , G ), is the number of times of the second-largest eigenvalue of A ( G ) appears. In 2...
详细信息
The multiplicity of the second-largest eigenvalue of the adjacency matrix A ( G ) of a connected graph G, denoted by m ( lambda 2 , G ), is the number of times of the second-largest eigenvalue of A ( G ) appears. In 2019, Jiang, Tidor, Yao, Zhang, and Zhao gave an upper bound on m ( lambda 2 , G ) for graphs G with bounded degrees, and applied it to solve a longstanding problem on equiangular lines. In this paper, we show that if G is a 3-connected planar graph or 2-connected outerplanar graph, then m ( lambda 2 , G ) <= delta ( G ), where delta ( G ) is the minimum degree of G. We further prove that if G is a connected planar graph, then m ( lambda 2 , G ) <= Delta ( G );if G is a connected outerplanar graph, then m ( lambda 2 , G ) <= max { 2 , Delta ( G ) - 1 }, where Delta ( G ) is the maximum degree of G. Moreover, these two upper bounds for connected planar graphs and outerplanar graphs, respectively, are best possible.
In the k-Apex problem the task is to find at most k vertices whose deletion makes the given graphplanar. The graphs for which there exists a solution form a minor closed class of graphs, hence by the deep results of ...
详细信息
In the k-Apex problem the task is to find at most k vertices whose deletion makes the given graphplanar. The graphs for which there exists a solution form a minor closed class of graphs, hence by the deep results of Robertson and Seymour (J. Comb. Theory, Ser. B 63(1):65-110, 1995;J. Comb. Theory, Ser. B 92(2):325-357, 2004), there is a cubic algorithm for every fixed value of k. However, the proof is extremely complicated and the constants hidden by the big-O notation are huge. Here we give a much simpler algorithm for this problem with quadratic running time, by iteratively reducing the input graph and then applying techniques for graphs of bounded treewidth.
We consider the following graph modification problem. Let the input consist of a graph G = (V, E), a weight function w: VUE -> N-0, a cost function c: V boolean OR E -> N-0 and a degree function 3: V -> N-0, ...
详细信息
We consider the following graph modification problem. Let the input consist of a graph G = (V, E), a weight function w: VUE -> N-0, a cost function c: V boolean OR E -> N-0 and a degree function 3: V -> N-0, together with three integers k(v), k(e) and C. The question is whether we can delete a set of vertices of total weight at most Icy and a set of edges of total weight at most ke so that the total cost of the deleted elements is at most C and every non deleted vertex v has degree delta(nu) in the resulting graph G'. We also consider the variant in which G' must be connected. Both problems are known to be NP-complete and W[1]-hard when parameterized by k(v), + k(e). We prove that, when restricted to planar graphs, they stay NP-complete but have polynomial kernels when parameterized by k(v) + k(e). (C) 2016 The Authors. Published by Elsevier Inc.
暂无评论