首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
An edge‐face coloring of a plane graph with edge set E and face set F is a coloring of the elements of EF so that adjacent or incident elements receive different colors. Borodin [Discrete Math 128(1–3):21–33, 1994] proved that every plane graph of maximum degree Δ?10 can be edge‐face colored with Δ + 1 colors. We extend Borodin's result to the case where Δ = 9. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:332‐346, 2011  相似文献   

2.
3.
We consider lower bounds on the the vertex‐distinguishing edge chromatic number of graphs and prove that these are compatible with a conjecture of Burris and Schelp 8 . We also find upper bounds on this number for certain regular graphs G of low degree and hence verify the conjecture for a reasonably large class of such graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 95–109, 2003  相似文献   

4.
5.
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 χ(G), is the least number of colors in an acyclic edge coloring of G. In this paper, we determine completely the acyclic edge chromatic number of outerplanar graphs. The proof is constructive and supplies a polynomial time algorithm to acyclically color the edges of any outerplanar graph G using χ(G) colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 22–36, 2010  相似文献   

6.
Let G be a planar graph and let g(G) and Δ(G) be its girth and maximum degree, respectively. We show that G has an edge‐partition into a forest and a subgraph H so that (i) Δ(H) ≤ 4 if g(G) ≥ 5; (ii) Δ(H) ≤ 2 if g(G) ≥ 7; (iii) Δ(H)≤ 1 if g(G) ≥ 11; (iv) Δ(H) ≤ 7 if G does not contain 4‐cycles (though it may contain 3‐cycles). These results are applied to find the following upper bounds for the game coloring number colg(G) of a planar graph G: (i) colg(G) ≤ 8 if g(G) ≥ 5; (ii) colg(G)≤ 6 if g(G) ≥ 7; (iii) colg(G) ≤ 5 if g(G) ≥ 11; (iv) colg(G) ≤ 11 if G does not contain 4‐cycles (though it may contain 3‐cycles). © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 307–317, 2002  相似文献   

7.
An Erratum has been published for this article in Journal of Graph Theory 48: 329–330, 2005 . Let M be a set of positive integers. The distance graph generated by M, denoted by G(Z, M), has the set Z of all integers as the vertex set, and edges ij whenever |i?j| ∈ M. We investigate the fractional chromatic number and the circular chromatic number for distance graphs, and discuss their close connections with some number theory problems. In particular, we determine the fractional chromatic number and the circular chromatic number for all distance graphs G(Z, M) with clique size at least |M|, except for one case of such graphs. For the exceptional case, a lower bound for the fractional chromatic number and an upper bound for the circular chromatic number are presented; these bounds are sharp enough to determine the chromatic number for such graphs. Our results confirm a conjecture of Rabinowitz and Proulx 22 on the density of integral sets with missing differences, and generalize some known results on the circular chromatic number of distance graphs and the parameter involved in the Wills' conjecture 26 (also known as the “lonely runner conjecture” 1 ). © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 129–146, 2004  相似文献   

8.
We consider colorings of the directed and undirected edges of a mixed multigraph G by an ordered set of colors. We color each undirected edge in one color and each directed edge in two colors, such that the color of the first half of a directed edge is smaller than the color of the second half. The colors used at the same vertex are all different. A bound for the minimum number of colors needed for such colorings is obtained. In the case where G has only directed edges, we provide a polynomal algorithm for coloring G with a minimum number of colors. An unsolved problem is formulated. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 267–273, 1999  相似文献   

9.
In 1968, Vizing conjectured that if G is a Δ‐critical graph with n vertices, then α(G)≤n/2, where α(G) is the independence number of G. In this paper, we apply Vizing and Vizing‐like adjacency lemmas to this problem and prove that α(G)<(((5Δ?6)n)/(8Δ?6))<5n/8 if Δ≥6. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 202‐212, 2011  相似文献   

10.
An edge‐coloring of a graph G is equitable if, for each vV(G), the number of edges colored with any one color incident with v differs from the number of edges colored with any other color incident with v by at most one. A new sufficient condition for equitable edge‐colorings of simple graphs is obtained. This result covers the previous results, which are due to Hilton and de Werra, verifies a conjecture made by Hilton recently, and substantially extends it to a more general class of graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:175‐197, 2011  相似文献   

11.
A graph G with maximum degree Δ and edge chromatic number χ′(G)>Δ is edge‐Δ‐critical if χ′(G?e)=Δ for every edge e of G. It is proved here that the vertex independence number of an edge‐Δ‐critical graph of order n is less than . For large Δ, this improves on the best bound previously known, which was roughly ; the bound conjectured by Vizing, which would be best possible, is . © 2010 Wiley Periodicals, Inc. J Graph Theory 66:98‐103, 2011  相似文献   

12.
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  相似文献   

13.
A proper coloring of the edges 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. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001  相似文献   

14.
The total chromatic number χT (G) of a graph G is the minimum number of colors needed to color the edges and the vertices of G so that incident or adjacent elements have distinct colors. We show that if G is a regular graph and d(G) 32 |V (G)| + 263 , where d(G) denotes the degree of a vertex in G, then χT (G) d(G) + 2.  相似文献   

15.
This article studies the circular chromatic number of a class of circular partitionable graphs. We prove that an infinite family of circular partitionable graphs G has . A consequence of this result is that we obtain an infinite family of graphs G with the rare property that the deletion of each vertex decreases its circular chromatic number by exactly 1. © 2006 Wiley Periodicals, Inc. J Graph Theory  相似文献   

16.
The r‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle C has at least min(|C|, r) colors. We show that (r ? 2)d is asymptotically almost surely (a.a.s.) an upper bound on the r‐acyclic edge chromatic number of a random d‐regular graph, for all constants r ≥ 4 and d ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 101–125, 2006  相似文献   

17.
In this article, we consider the circular chromatic number χc(G) of series‐parallel graphs G. It is well known that series‐parallel graphs have chromatic number at most 3. Hence, their circular chromatic numbers are at most 3. If a series‐parallel graph G contains a triangle, then both the chromatic number and the circular chromatic number of G are indeed equal to 3. We shall show that if a series‐parallel graph G has girth at least 2 ⌊(3k − 1)/2⌋, then χc(G) ≤ 4k/(2k − 1). The special case k = 2 of this result implies that a triangle free series‐parallel graph G has circular chromatic number at most 8/3. Therefore, the circular chromatic number of a series‐parallel graph (and of a K4‐minor free graph) is either 3 or at most 8/3. This is in sharp contrast to recent results of Moser [5] and Zhu [14], which imply that the circular chromatic number of K5‐minor free graphs are precisely all rational numbers in the interval [2, 4]. We shall also construct examples to demonstrate the sharpness of the bound given in this article. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 14–24, 2000  相似文献   

18.
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.  相似文献   

19.
The chromatic number of a graph G is defined as the minimum number of colors required for a vertex coloring where no two adjacent vertices are colored the same. The chromatic number of the dense random graph where is constant has been intensively studied since the 1970s, and a landmark result by Bollobás in 1987 first established the asymptotic value of . Despite several improvements of this result, the exact value of remains open. In this paper, new upper and lower bounds for are established. These bounds are the first ones that match each other up to a term of size o(1) in the denominator: they narrow down the coloring rate of to an explicit interval of length o(1), answering a question of Kang and McDiarmid.  相似文献   

20.
We consider graphs G with such that and for every edge e, so‐called critical graphs. Jakobsen noted that the Petersen graph with a vertex deleted, , is such a graph and has average degree only . He showed that every critical graph has average degree at least , and asked if is the only graph where equality holds. A result of Cariolaro and Cariolaro shows that this is true. We strengthen this average degree bound further. Our main result is that if G is a subcubic critical graph other than , then G has average degree at least . This bound is best possible, as shown by the Hajós join of two copies of .  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号