共查询到20条相似文献,搜索用时 15 毫秒
1.
Acyclic colorings of planar graphs 总被引:4,自引:0,他引:4
Branko Grünbaum 《Israel Journal of Mathematics》1973,14(4):390-408
A coloring of the vertices of a graph byk colors is called acyclic provided that no circuit is bichromatic. We prove that every planar graph has an acyclic coloring
with nine colors, and conjecture that five colors are sufficient. Other results on related types of colorings are also obtained;
some of them generalize known facts about “point-arboricity”.
Research supported in part by the Office of Naval Research under Grant N00014-67-A-0103-0003. 相似文献
2.
《European Journal of Combinatorics》2005,26(3-4):491-503
It is proved that graphs embedded in a surface with large nonseparating edge-width can be acyclically 8-colored. The condition on large nonseparating edge-width is expressed in terms of non-null-homologous circuits and is a weaker requirement than asking for large edge-width (which is based on homotopy). 相似文献
3.
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. 相似文献
4.
A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1.
This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation
of Shandong Province (Grant No. Y2008A20). 相似文献
5.
6.
A proper edge coloring of a graph G is said to be acyclic if there is no bicolored cycle in G.The acyclic edge chromatic number of G,denoted byχ′a(G),is the smallest number of colors in an acyclic edge coloring of G.Let G be a planar graph with maximum degree.In this paper,we show thatχ′a(G)+2,if G has no adjacent i-and j-cycles for any i,j∈{3,4,5},which implies a result of Hou,Liu and Wu(2012);andχ′a(G)+3,if G has no adjacent i-and j-cycles for any i,j∈{3,4,6}. 相似文献
7.
Acyclic edge colouring of planar graphs without short cycles 总被引:1,自引:0,他引:1
Mieczys?aw Borowiecki 《Discrete Mathematics》2010,310(9):1445-2495
Let G=(V,E) be any finite graph. A mapping C:E→[k] is called an acyclic edgek-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced in G by all the edges which have colour i or j, is acyclic. The smallest number k of colours, such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G, denoted by .In 2001, Alon et al. conjectured that for any graph G it holds that ; here Δ(G) stands for the maximum degree of G.In this paper we prove this conjecture for planar graphs with girth at least 5 and for planar graphs not containing cycles of length 4,6,8 and 9. We also show that if G is planar with girth at least 6. Moreover, we find an upper bound for the acyclic chromatic index of planar graphs without cycles of length 4. Namely, we prove that if G is such a graph, then . 相似文献
8.
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. 相似文献
9.
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. 相似文献
10.
Acyclic chromatic indices of planar graphs with large girth 总被引:1,自引:0,他引:1
An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a′(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.In this paper, we prove that every planar graph G with girth g(G) and maximum degree Δ has a′(G)=Δ if there exists a pair (k,m)∈{(3,11),(4,8),(5,7),(8,6)} such that G satisfies Δ≥k and g(G)≥m. 相似文献
11.
图G的一个无圈边着色是一个正常的边着色且不含双色的圈.图G的无圈边色数是图G的无圈边着色中所用色数的最小者.本文用反证法得到了不含5-圈的平面图G的无圈边色数的一个上界. 相似文献
12.
A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G such thatπ(v)∈L(v)for all v∈V.If G is acyclically L-colorable for any list assignment L with|L(v)|k for all v∈V(G),then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen(2009). 相似文献
13.
14.
O. V. Borodin D. G. Fon‐Der Flaass A. V. Kostochka A. Raspaud E. Sopena 《Journal of Graph Theory》2002,40(2):83-90
The acyclic list chromatic number of every planar graph is proved to be at most 7. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 83–90, 2002 相似文献
15.
16.
17.
18.
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. 相似文献
19.
A conjecture of G. Fan and A. Raspaud asserts that every bridgeless cubic graph contains three perfect matchings with empty intersection. We suggest a possible approach to problems of this type, based on the concept of a balanced join in an embedded graph. The method can be used to prove a special case of a conjecture of E. Máčajová and M. Škoviera on Fano colorings of cubic graphs. 相似文献
20.
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 article, we prove that every planar graph G without 4‐ and 5‐cycles, or without 4‐ and 6‐cycles is acyclically 5‐choosable. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 245–260, 2007 相似文献