共查询到20条相似文献,搜索用时 62 毫秒
1.
O. V. Borodin 《Journal of Applied and Industrial Mathematics》2011,5(1):31-43
Every planar graph is known to be acyclically 5-colorable (O.V.Borodin, 1976). Some sufficient conditions are also obtained
for a planar graph to be acyclically 4- and 3-colorable. In particular, the acyclic 4-colorability was proved for the following
planar graphs: without 3- and 4-cycles (O.V.Borodin, A.V. Kostochka, and D.R.Woodall, 1999), without 4-, 5-, and 6-cycles,
or without 4-, 5-, and 7-cycles, or without 4-, 5-, and intersecting 3-cycles (M. Montassier, A.Raspaud andW.Wang, 2006),
and without 4-, 5-, and 8-cycles (M. Chen and A.Raspaud, 2009). The purpose of this paper is to prove that each planar graph
without 4- and 5-cycles is acyclically 4-colorable. 相似文献
2.
A graph G is k-degenerate if each subgraph of G has a vertex of degree at most k. It is known that every simple planar graph with girth 6, or equivalently without 3-, 4-, and 5-cycles, is 2-degenerate. In this work, we investigate for which k every planar graph without 4-, 6-, … , and 2k-cycles is 2-degenerate. We determine that k is 5 and the result is tight since the truncated dodecahedral graph is a 3-regular planar graph without 4-, 6-, and 8-cycles. As a related result, we also show that every planar graph without 4-, 6-, 9-, and 10-cycles is 2-degenerate. 相似文献
3.
《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. 相似文献
4.
The conjecture on the acyclic 5-choosability of planar graphs (Borodin et al., 2002) as yet has been verified only for several
restricted classes of graphs: those of girth at least 5 (Montassier, Ochem, and Raspaud, 2006), without 4- and 5-cycles or
without 4- and 6-cycles (Montassier, Raspaud, and Wang, 2007), with neither 4-cycles nor chordal 6-cycles (Zhang and Xu, 2009),
with neither 4- cycles nor two 3-cycles at distance less than 3 (Chen and Wang, 2008), and with neither 4-cycles nor intersecting
3-cycles (Chen and Raspaud, 2010). Wang and Chen (2009) proved that the planar graphs without 4-cycles are acyclically 6-choosable.
We prove that a planar graph without 4-cycles is acyclically 5-choosable, which is a common strengthening of all above-mentioned
results. 相似文献
5.
A graph G=(V,E) is list L-colorable if for a given list assignment L={L(v):v∈V}, there exists a proper coloring c of G such that c(v)∈L(v) for all v∈V. If G is list L-colorable for every list assignment with |L(v)|?k for all v∈V, then G is said to be k-choosable.In this paper, we prove that (1) every planar graph either without 4- and 5-cycles, and without triangles at distance less than 4, or without 4-, 5- and 6-cycles, and without triangles at distance less than 3 is 3-choosable; (2) there exists a non-3-choosable planar graph without 4-cycles, 5-cycles, and intersecting triangles. These results have some consequences on the Bordeaux 3-color conjecture by Borodin and Raspaud [A sufficient condition for planar graphs to be 3-colorable. J. Combin. Theory Ser. B 88 (2003) 17-27]. 相似文献
6.
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. 相似文献
7.
Some structural properties of planar graphs without 4-cycles are investigated. By the structural properties, it is proved that every planar graph G without 4-cycles is edge-(Δ(G)+1)-choosable, which perfects the result given by Zhang and Wu: If G is a planar graph without 4-cycles, then G is edge-t-choosable, where t=7 if Δ(G)=5, and otherwise t=Δ(G)+1. 相似文献
8.
Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (Borodin et al. 2002) [7]. This conjecture if proved would imply both Borodin’s acyclic 5-color theorem (1979) and Thomassen’s 5-choosability theorem (1994). However, as yet it has been verified only for several restricted classes of graphs.Some sufficient conditions are also obtained for a planar graph to be acyclically 4-choosable and 3-choosable. In particular, acyclic 4-choosability was proved for the following planar graphs: without 3-cycles and 4-cycles (Montassier, 2006 [23]), without 4-cycles, 5-cycles and 6-cycles (Montassier et al. 2006 [24]), and either without 4-cycles, 6-cycles and 7-cycles, or without 4-cycles, 6-cycles and 8-cycles (Chen et al. 2009 [14]).In this paper it is proved that each planar graph with neither 4-cycles nor 6-cycles adjacent to a triangle is acyclically 4-choosable, which covers these four results. 相似文献
9.
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]. 相似文献
10.
Steinberg猜想既没有4-圈又没有5-圈的平面图是3色可染的. Xu, Borodin等人各自独立地证明了既没有相邻三角形又没有5-和7-圈的平面图是3 色可染的. 作为这一结果的推论, 没有4-, 5-和7-圈的平面图是3色可染的. 本文证明一个比此推论更接近Steinberg猜想的结果, 设G是一个既没有4-圈又没有5-圈的平面图, 若对每一个k∈{3, 6, 7}, G都不含(k, 7)-弦, 则G是3色可染的, 这里的(k, 7)-弦是指长度为7+k-2的圈的一条弦, 它的两个端点将圈分成两条路, 一条路的长度为6, 另一条路的长度为k-1. 相似文献
11.
O. V. Borodin 《Journal of Applied and Industrial Mathematics》2010,4(4):490-495
Every planar graph is known to be acyclically 5-colorable (O. V. Borodin, 1976), which bound is precise. Some sufficient conditions
are also obtained for a planar graph to be acyclically 4-colorable. In particular, the acyclic 4-colorabilitywas proved for
the following planar graphs: without 3- and 4-cycles (O. V. Borodin, A. V. Kostochka, and D. R. Woodall, 1999), without 4-,
5-, and 6-cycles (M. Montassier, A. Raspaud, and W. Wang, 2006), and either without 4-, 6-, and 7-cycles or without 4-, 6-,
and 8-cycles (M. Chen, A. Raspaud, and W. Wang, 2009). In this paper it is proved that each planar graph with neither 4-cycles
nor 6-cycles is acyclically 4-colorable. 相似文献
12.
13.
The minimum number of colors needed to properly color the vertices and edges of a graph G is called the total chromatic number of G and denoted by χ’’ (G). It is shown that if a planar graph G has maximum degree Δ≥9, then χ’’ (G) = Δ + 1. In this paper, we prove that if G is a planar graph with maximum degree 8 and without intersecting chordal 4-cycles, then χ ’’(G) = 9. 相似文献
14.
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. 相似文献
15.
《Discrete Mathematics》2007,307(7-8):1013-1015
Steinberg's question from 1975 whether every planar graph without 4- and 5-cycles is 3-colorable is still open. In this paper the analogous question for 3-choosability of such graphs is answered to the negative. 相似文献
16.
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. 相似文献
17.
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. 相似文献
18.
《Applied Mathematics Letters》2001,14(3):269-273
A graph G is called (k, d)*-choosable if, for every list assignment L satisfying |L(v)| = k for all v ϵ V(G), there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. In this note, we prove that every planar graph without 4-cycles and l-cycles for some l ϵ {5, 6, 7} is (3, 1)*-choosable. 相似文献
19.
O. V. Borodin 《Journal of Applied and Industrial Mathematics》2010,4(2):158-162
Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (O. V. Borodin
et al., 2002). This conjecture if proved would imply both Borodin’s acyclic 5-color theorem (1979) and Thomassen’s 5-choosability
theorem (1994). However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions
are also obtained for a planar graph to be acyclically 4- and 3-colorable. In particular, a planar graph of girth at least
7 is acyclically 3-colorable (O. V. Borodin, A. V. Kostochka and D. R. Woodall, 1999) and acyclically 3-choosable (O. V. Borodin
et. al, 2009). A natural measure of sparseness, introduced by Erdős and Steinberg, is the absence of k-cycles, where 4 ≤ k ≤ S. Here, we prove that every planar graph without cycles of length from 4 to 12 is acyclically 3-choosable. 相似文献
20.
Richard Steinberg 《Journal of Graph Theory》1984,8(2):277-285
Heawood proved that every planar graph with no 1-cycles is vertex 5-colorable, which is equivalent to the statement that every planar graph with no 1-bonds has a nowhere-zero 5-flow. Tutte has conjectured that every graph with no 1-bonds has a nowhere-zero 5-flow. We show that Tutte's 5-Flow Conjecture is true for all graphs embeddable in the real projective plane. 相似文献