共查询到10条相似文献,搜索用时 62 毫秒
1.
A total k-coloring of a graph G is a coloring of V(G) ∪ E(G) using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number χ'(G) is the smallest integer k such that G has a total k-coloring. It is known 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 a fan of four adjacent 3-cycles, then χ'(G) = 9. 相似文献
2.
Nicolas Roussel 《Discrete Applied Mathematics》2011,159(1):87-89
Let G be a planar graph with maximum degree 4. It is known that G is 8-totally choosable. It has been recently proved that if G has girth g?6, then G is 5-totally choosable. In this note we improve the first result by showing that G is 7-totally choosable and complete the latter one by showing that G is 6-totally choosable if G has girth at least 5. 相似文献
3.
The total chromatic number χT(G) of a graph G is the least number of colors needed to color the vertices and the edges of G such that no adjacent or incident elements receive the same color. The Total Coloring Conjecture(TCC) states that for every simple graph G, χT(G)≤Δ(G)+2. In this paper, we show that χT(G)=Δ(G)+1 for all pseudo-Halin graphs with Δ(G)=4 and 5. 相似文献
4.
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 相似文献
5.
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. 相似文献
6.
It is proved that a planar graph with maximum degree Δ ≥ 11 has total (vertex-edge) chromatic number $Delta; + 1. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 53–59, 1997 相似文献
7.
The total chromatic number χT(G) of a graph G is the minimum number of colors needed to color the elements (vertices and edges) of G such that no adjacent or incident pair of elements receive the same color. G is called Type 1 if χT(G)=Δ(G)+1. In this paper we prove that the join of a complete inequibipartite graph Kn1,n2 and a path Pm is of Type 1. 相似文献
8.
A local coloring of a graph G is a function c:V(G)→N having the property that for each set S⊆V(G) with 2≤|S|≤3, there exist vertices u,v∈S such that |c(u)−c(v)|≥mS, where mS is the number of edges of the induced subgraph 〈S〉. The maximum color assigned by a local coloring c to a vertex of G is called the value of c and is denoted by χ?(c). The local chromatic number of G is χ?(G)=min{χ?(c)}, where the minimum is taken over all local colorings c of G. The local coloring of graphs was introduced by Chartrand et al. [G. Chartrand, E. Salehi, P. Zhang, On local colorings of graphs, Congressus Numerantium 163 (2003) 207-221]. In this paper the local coloring of Kneser graphs is studied and the local chromatic number of the Kneser graph K(n,k) for some values of n and k is determined. 相似文献
9.
10.
An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). It was conjectured by Alon, Sudakov, and Zaks that for any simple and finite graph G, a′(G)?Δ + 2, where Δ=Δ(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Δ(G)?4, with the additional restriction that m?2n?1, where n is the number of vertices and m is the number of edges in G. Note that for any graph G, m?2n, when Δ(G)?4. It follows that for any graph G if Δ(G)?4, then a′(G)?7. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 192–209, 2009 相似文献