共查询到20条相似文献,搜索用时 15 毫秒
1.
Let G be a planar graph without adjacent 3-cycles, that is, two cycles of length 3 are not incident with a common edge. In this paper, it is proved that the total coloring conjecture is true for G; moreover, if Δ(G)≥9, then the total chromatic number χ″(G) of G is Δ(G)+1. Some other related results are obtained, too. 相似文献
2.
Total colorings and list total colorings of planar graphs without intersecting 4-cycles 总被引:1,自引:0,他引:1
Suppose that G is a planar graph with maximum degree Δ and without intersecting 4-cycles, that is, no two cycles of length 4 have a common vertex. Let χ″(G), and denote the total chromatic number, list edge chromatic number and list total chromatic number of G, respectively. In this paper, it is proved that χ″(G)=Δ+1 if Δ≥7, and and if Δ(G)≥8. Furthermore, if G is a graph embedded in a surface of nonnegative characteristic, then our results also hold. 相似文献
3.
A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define for and We say that is -colorable if has a 2-coloring such that is an empty set or the induced subgraph has the maximum degree at most for and Let be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether is -colorable is NP-complete for every positive integer Moreover, we construct non--colorable planar graphs without 4-cycles and 5-cycles for every positive integer In contrast, we prove that is -colorable where and 相似文献
4.
It is known that planar graphs without cycles of length 4, i, j, or 9 with 4<i<j<9, except that i=7 and j=8, are 3-choosable. This paper proves that planar graphs without cycles of length 4, 7, 8, or 9 are also 3-choosable. 相似文献
5.
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 . 相似文献
6.
Planar graphs without 5-cycles or without 6-cycles 总被引:1,自引:0,他引:1
Let G be a planar graph without 5-cycles or without 6-cycles. In this paper, we prove that if G is connected and δ(G)≥2, then there exists an edge xy∈E(G) such that d(x)+d(y)≤9, or there is a 2-alternating cycle. By using the above result, we obtain that (1) its linear 2-arboricity , (2) its list total chromatic number is Δ(G)+1 if Δ(G)≥8, and (3) its list edge chromatic number is Δ(G) if Δ(G)≥8. 相似文献
7.
A graph G is equitably k-choosable if for any k-uniform list assignment L, there exists an L-colorable of G such that each color appears on at most vertices. Kostochka, Pelsmajer and West introduced this notion and conjectured that G is equitably k-choosable for k>Δ(G). We prove this for planar graphs with Δ(G)≥6 and no 4- or 6-cycles. 相似文献
8.
Hua Cai 《数学学报(英文版)》2015,31(12):1951-1962
A k-total-coloring of a graph G is a coloring of vertices and edges of G using k colors such that no two adjacent or incident elements receive the same color.In this paper,it is proved that if G is a planar graph with Δ(G) ≥ 7 and without chordal 7-cycles,then G has a(Δ(G) + 1)-total-coloring. 相似文献
9.
Yingqian Wang 《Discrete Mathematics》2010,310(1):147-373
It is shown that a planar graph without cycles of length 4, 5, 8, or 9 is 3-choosable. 相似文献
10.
A proper vertex coloring of a graph G=(V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L-list colorable if for a given list assignment L={L(v):v∈V}, there exists a proper acyclic coloring ? of G such that ?(v)∈L(v) for all v∈V(G). If G is acyclically L-list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k-choosable. In this paper it is proved that every planar graph with neither 4-cycles nor chordal 6-cycles is acyclically 5-choosable. This generalizes the results of [M. Montassier, A. Raspaud, W. Wang, Acyclic 5-choosability of planar graphs without small cycles, J. Graph Theory 54 (2007) 245-260], and a corollary of [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (4) (2006) 281-300]. 相似文献
11.
A proper vertex coloring of a graph G=(V,E) is acyclic if G contains no bicolored cycle. Given a list assignment L={L(v)∣v∈V} of G, we say G is acyclically L-list colorable if there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L-list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k-choosable. In this paper we prove that planar graphs without 4, 7, and 8-cycles are acyclically 4-choosable. 相似文献
12.
Min Chen 《Discrete Mathematics》2008,308(24):6216-6225
A proper vertex coloring of a graph G=(V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L-list colorable if for a given list assignment L={L(v):v∈V}, there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L-list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k-choosable. In this paper we prove that every planar graph without 4-cycles and without two 3-cycles at distance less than 3 is acyclically 5-choosable. This improves a result in [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (2006) 281-300], which says that planar graphs of girth at least 5 are acyclically 5-choosable. 相似文献
13.
《Discrete Mathematics》2023,346(1):113192
Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. This conjecture is disproved by constructing a planar graph with no cycles of length four or five but intersecting triangles. Jin et al. proved that plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable [SIAM J. Discrete Math. 31 (3) (2017) 1836–1847]. In this paper, we point out a mistake of their proof and give an improved proof. 相似文献
14.
In this paper we prove that every planar graph without cycles of length 4, 5, 6 and 8 is 3-colorable. 相似文献
15.
16.
A graph G is k-choosable if every vertex of G can be properly colored whenever every vertex has a list of at least k available colors. Grötzsch’s theorem [4] states that every planar triangle-free graph is 3-colorable. However, Voigt [M. Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Math. 146 (1995) 325-328] gave an example of such a graph that is not 3-choosable, thus Grötzsch’s theorem does not generalize naturally to choosability. We prove that every planar triangle-free graph without 7- and 8-cycles is 3-choosable. 相似文献
17.
18.
Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable 总被引:1,自引:0,他引:1
It is known that planar graphs without cycles of length from 4 to 7 are 3-colorable (Borodin et al., 2005) [13] and that planar graphs in which no triangles have common edges with cycles of length from 4 to 9 are 3-colorable (Borodin et al., 2006) [11]. We give a common extension of these results by proving that every planar graph in which no triangles have common edges with k-cycles, where k∈{4,5,7} (or, which is equivalent, with cycles of length 3, 5 and 7), is 3-colorable. 相似文献
19.
Let Δ denote the maximum degree of a graph. Fiam?ík first and then Alon et al. again conjectured that every graph is acyclically edge (Δ+2)-colorable. Even for planar graphs, this conjecture remains open. It is known that every triangle-free planar graph is acyclically edge (Δ+5)-colorable. This paper proves that every planar graph without intersecting triangles is acyclically edge (Δ+4)-colorable. 相似文献
20.
Yongzhu Chen 《Discrete Mathematics》2009,309(8):2233-2163
Let G be a plane graph having no 5-cycles with a chord. If either Δ≥6, or Δ=5 and G contains no 4-cycles with a chord or no 6-cycles with a chord, then G is edge-(Δ+1)-choosable, where Δ denotes the maximum degree of G. 相似文献