共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
Michael A. Bekos Emilio Di Giacomo Walter Didimo Giuseppe Liotta Fabrizio Montecchiani Chrysanthi Raftopoulou 《Discrete Mathematics》2019,342(4):1038-1047
A topological graph is a graph drawn in the plane. A topological graph is -plane, , if each edge is crossed at most times. We study the problem of partitioning the edges of a -plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for , we focus on optimal 2-plane and on optimal 3-plane graphs, which are 2-plane and 3-plane graphs with maximum density. We prove the following results. (i) It is not possible to partition the edges of a simple (i.e., with neither self-loops nor parallel edges) optimal 2-plane graph into a 1-plane graph and a forest, while (ii) an edge partition formed by a 1-plane graph and two plane forests always exists and can be computed in linear time. (iii) There exist efficient algorithms to partition the edges of a simple optimal 2-plane graph into a 1-plane graph and a plane graph with maximum vertex degree at most 12, or with maximum vertex degree at most 8 if the optimal2-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) There exists an infinite family of simple optimal 2-plane graphs such that in any edge partition composed of a 1-plane graph and a plane graph, the plane graph has maximum vertex degree at least 6 and the 1-plane graph has maximum vertex degree at least 12. (v) Every optimal 3-plane graph whose crossing-free edges form a biconnected graph can be decomposed, in linear time, into a 2-plane graph and two plane forests. 相似文献
3.
《Discrete Mathematics》2021,344(12):112600
An -colored-mixed graph is a graph having m colors of arcs and n colors of edges. We do not allow two arcs or edges to have the same endpoints. A homomorphism from an -colored-mixed graph G to another -colored-mixed graph H is a morphism such that each edge (resp. arc) of G is mapped to an edge (resp. arc) of H of the same color (and orientation). An -colored-mixed graph T is said to be -universal if every graph in (the planar -colored-mixed graphs with girth at least g) admits a homomorphism to T.We show that planar -universal graphs do not exist for (and any value of g) and find a minimal (in the number vertices) planar -universal graphs in the other cases. 相似文献
4.
In Thomassen (1995) [4], Thomassen proved that planar graphs of girth at least 5 are 3-choosable. In Li (2009) [3], Li improved Thomassen’s result by proving that planar graphs of girth 4 with no 4-cycle sharing a vertex with another 4- or 5-cycle are 3-choosable. In this paper, we prove that planar graphs of girth 4 with no 4-cycle sharing an edge with another 4- or 5-cycle are 3-choosable. It is clear that our result strengthens Li’s result. 相似文献
5.
6.
We view an undirected graph as a symmetric digraph, where each edge is replaced by two opposite arcs and . Assume is an inverse closed subset of permutations of positive integers. We say is --colourable if for any mapping with , there is a mapping such that for each arc . The concept of --colourable is a common generalization of several other colouring concepts. This paper is focused on finding the sets such that every triangle-free planar graph is -3-colourable. Such a set is called TFP-good. Grötzsch’s theorem is equivalent to say that is TFP-good. We prove that for any inverse closed subset of which is not isomorphic to , is TFP-good if and only if either or there exists such that for each , . It remains an open question to determine whether or not is TFP-good. 相似文献
7.
8.
Xiangwen Li 《Discrete Mathematics》2009,309(8):2424-417
Let G be a plane graph of girth at least 4. Two cycles of G are intersecting if they have at least one vertex in common. In this paper, we show that if a plane graph G has neither intersecting 4-cycles nor a 5-cycle intersecting with any 4-cycle, then G is 3-choosable, which extends one of Thomassen’s results [C. Thomassen, 3-list-coloring planar graphs of girth 5, J. Combin. Theory Ser. B 64 (1995) 101-107]. 相似文献
9.
In this article, we use a unified approach to prove several classes of planar graphs are DP-3-colorable, which extend the corresponding results on 3-choosability. 相似文献
10.
11.
Haiyang Zhu Lianying Miao Sheng Chen Xinzhong Lü Wenyao Song 《Discrete Mathematics》2018,341(8):2211-2219
Let be the set of all positive integers. A list assignment of a graph is a function that assigns each vertex a list for all . We say that is --choosable if there exists a function such that for all , if and are adjacent, and if and are at distance 2. The list--labeling number of is the minimum such that for every list assignment , is --choosable. We prove that if is a planar graph with girth
and its maximum degree is large enough, then . There are graphs with large enough and having . 相似文献
12.
A -list assignment of a graph is a mapping that assigns to each vertex a list of at least colors satisfying for each edge . A graph is -choosable if there exists an -coloring of for every -list assignment . This concept is also known as choosability with separation. In this paper, we prove that any planar graph is -choosable if any -cycle is not adjacent to a -cycle, where and . 相似文献
13.
14.
In 1995, Voigt constructed a planar triangle-free graph that is not 3-list-colorable. It has 166 vertices. Gutner then constructed such a graph with 164 vertices. We present two more graphs with these properties. The first graph has 97 vertices and a failing list assignment using triples from a set of six colors, while the second has 109 vertices and a failing list assignment using triples from a set of five colors. 相似文献
15.
16.
17.
In 2009, Kyaw proved that every -vertex connected -free graph with contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected -free graphs. We show that every -vertex connected -free graph with contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “” is best possible. 相似文献
18.
In this paper, we mainly prove that planar graphs without 4-, 7- and 9-cycles are 3-colorable. 相似文献
19.
DP-coloring (also known as correspondence coloring) is a generalization of list coloring introduced by Dvo?ák and Postle in 2017. In this paper, we prove that every planar graph without 4-cycles adjacent to -cycles is DP-4-colorable for and 6. As a consequence, we obtain two new classes of 4-choosable planar graphs. We use identification of vertices in the proof, and actually prove stronger statements that every pre-coloring of some short cycles can be extended to the whole graph. 相似文献
20.
《Discrete Mathematics》2022,345(4):112790
DP-coloring of graphs as a generalization of list coloring was introduced by Dvo?ák and Postle (2018). In this paper, we show that every planar graph without intersecting 5-cycles is DP-4-colorable, which improves the result of Hu and Wu (2017), who proved that every planar graph without intersecting 5-cycles is 4-choosable, and the results of Kim and Ozeki (2018). 相似文献