共查询到20条相似文献,搜索用时 15 毫秒
1.
《Discrete Mathematics》2022,345(9):112942
A graph G is k-degenerate if every subgraph of G has a vertex with degree at most k. Using the Euler's formula, one can obtain that planar graphs without 3-cycles are 3-degenerate. Wang and Lih, and Fijav? et al. proved the analogue results for planar graphs without 5-cycles and planar graphs without 6-cycles, respectively. Recently, Liu et al. showed that planar graphs without 3-cycles adjacent to 5-cycles are 3-degenerate. In this work, we generalized all aforementioned results by showing that planar graphs without mutually adjacent 3-,5-, and 6-cycles are 3-degenerate. A graph G without mutually adjacent 3-,5-, and 6-cycles means that G cannot contain three graphs, say , and , where is a 3-cycle, is a 5-cycle, and is a 6-cycle such that each pair of , and are adjacent. As an immediate consequence, we have that every planar graph without mutually adjacent 3-,5-, and 6-cycles is DP-4-colorable. This consequence also generalizes the result by Chen et al that planar graphs without 5-cycles adjacent to 6-cycles are DP-4-colorable. 相似文献
2.
3.
Jie Hu Guanghui Wang Jianliang Wu Donglei Yang Xiaowei Yu 《Discrete Mathematics》2019,342(5):1392-1402
Let be a positive integer. An adjacent vertex distinguishing (for short, AVD) total--coloring of a graph is a proper total--coloring of such that any two adjacent vertices have different color sets, where the color set of a vertex contains the color of and the colors of its incident edges. It was conjectured that any graph with maximum degree has an AVD total-()-coloring. The conjecture was confirmed for any graph with maximum degree at most 4 and any planar graph with maximum degree at least 10. In this paper, we verify the conjecture for all planar graphs with maximum degree at least 9. Moreover, we prove that any planar graph with maximum degree at least 10 has an AVD total-()-coloring and the bound is sharp. 相似文献
4.
5.
In this paper, we investigate the signed graph version of Erdös problem: Is there a constant such that every signed planar graph without -cycles, where , is 3-colorable and prove that each signed planar graph without cycles of length from 4 to 8 is 3-colorable. 相似文献
6.
An incidence of a graph is a pair where is a vertex of and is an edge of incident to . Two incidences and of are adjacent whenever (i) , or (ii) , or (iii) or . An incidence-coloring of is a mapping from the set of incidences of to a set of colors such that every two adjacent incidences receive distinct colors. The notion of incidence coloring has been introduced by Brualdi and Quinn Massey (1993) from a relation to strong edge coloring, and since then, has attracted a lot of attention by many authors.On a list version of incidence coloring, it was shown by Benmedjdoub et al. (2017) that every Hamiltonian cubic graph is incidence 6-choosable. In this paper, we show that every cubic (loopless) multigraph is incidence 6-choosable. As a direct consequence, it implies that the list strong chromatic index of a -bipartite graph is at most 6, where a (2,3)-bipartite graph is a bipartite graph such that one partite set has maximum degree at most 2 and the other partite set has maximum degree at most 3. 相似文献
7.
An edge of a -connected graph is said to be -contractible if its contraction results in a -connected graph. A -connected graph without -contractible edge is said to be contraction critically -connected. Y. Egawa and W. Mader, independently, showed that the minimum degree of a contraction critical -connected graph is at most . Hence, the minimum degree of a contraction critical 8-connected graph is either 8 or 9. This paper shows that a graph is a contraction critical 8-connected graph with minimum degree 9 if and only if is the strong product of a contraction critical 4-connected graph and . 相似文献
8.
A star edge coloring of a graph is a proper edge coloring such that every connected 2-colored subgraph is a path with at most 3 edges. Deng et al. and Bezegová et al. independently show that the star chromatic index of a tree with maximum degree is at most , which is tight. In this paper, we study the list star edge coloring of -degenerate graphs. Let be the list star chromatic index of : the minimum such that for every -list assignment for the edges, has a star edge coloring from . By introducing a stronger coloring, we show with a very concise proof that the upper bound on the star chromatic index of trees also holds for list star chromatic index of trees, i.e. for any tree with maximum degree . And then by applying some orientation technique we present two upper bounds for list star chromatic index of -degenerate graphs. 相似文献
9.
《Discrete Mathematics》2019,342(5):1471-1480
11.
A well-known result from the 1960 paper of Erdős and Rényi (1960) [2] tells us that the almost sure theory for first order language on the random graph sequence is not complete. Our paper proposes and proves what the complete set of completions of the almost sure theory for should be. The almost sure theory consists of two sentence groups: the first states that all the components are trees or unicyclic components, and the second states that, given any and any finite tree , there are at least components isomorphic to . We define a -completion of to be a first order property , such that if holds for a graph (which indicates that the property described in sentence is satisfied by the graph, and for every sentence in the theory , the property described by is also satisfied by the graph), we can fully describe the first order sentences of quantifier depth that hold for that graph. We show that a -completion specifies the numbers, up to “cutoff” , of the (finitely many) unicyclic component types of given parameters (that only depend on ) that the graph contains. A complete set of -completions is then the finite collection of all possible -completions. 相似文献
13.
Adam Kabela 《Discrete Mathematics》2019,342(1):55-63
We show that every -tree of toughness greater than is Hamilton-connected for . (In particular, chordal planar graphs of toughness greater than 1 are Hamilton-connected.) This improves the result of Broersma et al. (2007) and generalizes the result of Böhme et al. (1999).On the other hand, we present graphs whose longest paths are short. Namely, we construct 1-tough chordal planar graphs and 1-tough planar 3-trees, and we show that the shortness exponent of the class is 0, at most , respectively. Both improve the bound of Böhme et al. Furthermore, the construction provides -trees (for ) of toughness greater than 1. 相似文献
14.
15.
《Discrete Mathematics》2023,346(4):113288
Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner, 1977) states that colors are sufficient to square color every planar graph of maximum degree Δ. This conjecture has been proven asymptotically for graphs with large maximum degree. We consider here planar graphs with small maximum degree and show that colors are sufficient, which improves the best known bounds when . 相似文献
16.
We consider the structure of -free subgraphs of graphs with high minimal degree. We prove that for every there exists an so that the following holds. For every graph with chromatic number from which one can delete an edge and reduce the chromatic number, and for every graph on vertices in which all degrees are at least , any subgraph of which is -free and contains the maximum number of copies of the complete graph is -colorable.We also consider several extensions for the case of a general forbidden graph of a given chromatic number, and for subgraphs maximizing the number of copies of balanced blowups of complete graphs. 相似文献
17.
Hemanshu Kaul Jeffrey A. Mudrock Michael J. Pelsmajer Benjamin Reiniger 《Discrete Mathematics》2019,342(8):2371-2383
In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. A -assignment for a graph specifies a list of available colors for each vertex of . An -coloring assigns a color to each vertex from its list . For each color , let be the number of vertices whose list contains . A proportional-coloring of is a proper -coloring in which each color is used or times. A graph is proportionally-choosable if a proportional -coloring of exists whenever is a -assignment for . We show that if a graph is proportionally -choosable, then every subgraph of is also proportionally -choosable and also is proportionally -choosable, unlike equitable choosability for which analogous claims would be false. We also show that any graph is proportionally -choosable whenever , and we use matching theory to completely characterize the proportional choosability of stars and the disjoint union of cliques. 相似文献
18.
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 . 相似文献
19.
Aleksander Czarnecki 《Journal of Pure and Applied Algebra》2019,223(3):1161-1166
We prove that every maximal ideal in the ring of k-regulous functions, , on a smooth real affine algebraic variety of dimension is not finitely generated. 相似文献
20.
Define a -star to be the complete bipartite graph . In a 2014 article, Hoffman and Roberts prove that a partial -star decomposition of can be embedded in a -star decomposition of where is at most if is odd and if is even. In our work, we offer a straightforward construction for embedding partial -star designs and lower these bounds to and , respectively. 相似文献