共查询到20条相似文献,搜索用时 46 毫秒
1.
A graph G is class II, if its chromatic index is at least Δ + 1. Let H be a maximum Δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ‐edge‐colorable subgraph. Simple graphs have a maximum Δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
2.
O. V. Borodin A. O. Ivanova M. Montassier P. Ochem A. Raspaud 《Journal of Graph Theory》2010,65(2):83-93
A graph G is (k,0)‐colorable if its vertices can be partitioned into subsets V1 and V2 such that in G[V1] every vertex has degree at most k, while G[V2] is edgeless. For every integer k?0, we prove that every graph with the maximum average degree smaller than (3k+4)/(k+2) is (k,0)‐colorable. In particular, it follows that every planar graph with girth at least 7 is (8, 0)‐colorable. On the other hand, we construct planar graphs with girth 6 that are not (k,0)‐colorable for arbitrarily large k. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:83–93, 2010 相似文献
3.
For a pair of integers k, l≥0, a graph G is (k, l)‐colorable if its vertices can be partitioned into at most k independent sets and at most l cliques. The bichromatic number χb(G) of G is the least integer r such that for all k, l with k+l=r, G is (k, l)‐colorable. The concept of bichromatic numbers simultaneously generalizes the chromatic number χ(G) and the clique covering number θ(G), and is important in studying the speed of hereditary properties and edit distances of graphs. It is easy to see that for every graph G the bichromatic number χb(G) is bounded above by χ(G)+θ(G)?1. In this article, we characterize all graphs G for which the upper bound is attained, i.e., χb(G)=χ(G)+θ(G)?1. It turns out that all these graphs are cographs and in fact they are the critical graphs with respect to the (k, l)‐colorability of cographs. More specifically, we show that a cograph H is not (k, l)‐colorable if and only if H contains an induced subgraph G with χ(G)=k+1, θ(G)=l+1 and χb(G)=k+l+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 263–269, 2010 相似文献
4.
Uniquely vertex colorable graphs and uniquely edge colorable graphs have been studied extensively by different authors. The literature on the similar problem for total coloring is void. In this paper we study this concept and, among other results, we prove that if a graph G ≠ K 2 is uniquely total colorable, then χ″(G) = Δ + 1. Our results support the following conjecture: empty graphs, paths, and cycles of order 3k, k a natural number, are the only uniquely total colorable graphs. 相似文献
5.
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 G without 4‐cycles is acyclically 6‐choosable. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 307–323, 2009 相似文献
6.
Suppose G is a graph embedded in Sg with width (also known as edge width) at least 264(2g−1). If P ⊆ V(G) is such that the distance between any two vertices in P is at least 16, then any 5‐coloring of P extends to a 5‐coloring of all of G. We present similar extension theorems for 6‐ and 7‐chromatic toroidal graphs, for 3‐colorable large‐width graphs embedded on Sg with every face even‐sided, and for 4‐colorable large‐width Eulerian triangulations. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 105–116, 2001 相似文献
7.
Glenn G. Chappell 《Journal of Graph Theory》1999,32(4):390-393
Let G be an n-vertex graph with list-chromatic number χℓ. Suppose that each vertex of G is assigned a list of t colors. Albertson, Grossman, and Haas [1] conjecture that at least tn/χℓ vertices can be colored from these lists. We prove a lower bound for the number of colorable vertices. As a corollary, we show that at least of the conjectured number can be colored. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 390–393, 1999 相似文献
8.
9.
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 相似文献
10.
A graph G is minimal harmoniously colorable if it has a proper vertex coloring in which each pair of colors occurs exactly once on an edge. In particular, if D is a 2-design we consider the graph G whose vertices are the points and blocks of D and where two vertices of G are adjacent if and only if the corresponding elements of D are incident. It will be shown that if D is symmetric then G is minimal harmoniously colorable if and only if D is a Hadamard design with corresponding Hadamard matrix of a certain form. We obtain some results if D is nonsymmetric, and construct two classes of nonsymmetric minimal harmoniously colorable designs. © 1994 John Wiley & Sons, Inc. 相似文献
11.
Suppose G=(V, E) is a graph and p ≥ 2q are positive integers. A (p, q)‐coloring of G is a mapping ?: V → {0, 1, …, p‐1} such that for any edge xy of G, q ≤ |?(x)‐?(y)| ≤ p‐q. A color‐list is a mapping L: V → ({0, 1, …, p‐1}) which assigns to each vertex v a set L(v) of permissible colors. An L‐(p, q)‐coloring of G is a (p, q)‐coloring ? of G such that for each vertex v, ?(v) ∈ L(v). We say G is L‐(p, q)‐colorable if there exists an L‐(p, q)‐coloring of G. A color‐size‐list is a mapping ? which assigns to each vertex v a non‐negative integer ?(v). We say G is ?‐(p, q)‐colorable if for every color‐list L with |L(v)| = ?(v), G is L‐(p, q)‐colorable. In this article, we consider list circular coloring of trees and cycles. For any tree T and for any p ≥ 2q, we present a necessary and sufficient condition for T to be ?‐(p, q)‐colorable. For each cycle C and for each positive integer k, we present a condition on ? which is sufficient for C to be ?‐(2k+1, k)‐colorable, and the condition is sharp. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 249–265, 2007 相似文献
12.
A graph G is a quasi‐line graph if for every vertex v ∈ V(G), the set of neighbors of v in G can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. Hadwiger's conjecture states that if a graph G is not t‐colorable then it contains Kt + 1 as a minor. This conjecture has been proved for line graphs by Reed and Seymour. We extend their result to all quasi‐line graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 17–33, 2008 相似文献
13.
《Journal of Graph Theory》2018,87(4):460-474
An odd k‐edge‐coloring of a graph G is a (not necessarily proper) edge‐coloring with at most k colors such that each nonempty color class induces a graph in which every vertex is of odd degree. Pyber (1991) showed that every simple graph is odd 4‐edge‐colorable, and Lužar et al. (2015) showed that connected loopless graphs are odd 5‐edge‐colorable, with one particular exception that is odd 6‐edge‐colorable. In this article, we prove that connected loopless graphs are odd 4‐edge‐colorable, with two particular exceptions that are respectively odd 5‐ and odd 6‐edge‐colorable. Moreover, a color class can be reduced to a size at most 2. 相似文献
14.
Yue Zhao 《Journal of Graph Theory》2000,33(3):140-143
In this article, we show that there exists an integer k(Σ) ≥ 5 such that, if G is a graph embedded in a surface Σ without i‐circuits, 4 ≤ i ≤ k(Σ), then G is 3‐colorable. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 140–143, 2000 相似文献
15.
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 article we prove that every planar graph without 4‐cycles and without intersecting triangles is acyclically 5‐choosable. This improves the result in [M. Chen and W. Wang, Discrete Math 308 (2008), 6216–6225], which says that every planar graph without 4‐cycles and without two triangles at distance less than 3 is acyclically 5‐choosable. © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
16.
Given a 3‐colorable graph G together with two proper vertex 3‐colorings α and β of G, consider the following question: is it possible to transform α into β by recoloring vertices of G one at a time, making sure that all intermediate colorings are proper 3‐colorings? We prove that this question is answerable in polynomial time. We do so by characterizing the instances G, α, β where the transformation is possible; the proof of this characterization is via an algorithm that either finds a sequence of recolorings between α and β, or exhibits a structure which proves that no such sequence exists. In the case that a sequence of recolorings does exist, the algorithm uses O(|V(G)|2) recoloring steps and in many cases returns a shortest sequence of recolorings. We also exhibit a class of instances G, α, β that require Ω(|V(G)|2) recoloring steps. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 69‐82, 2011 相似文献
17.
18.
Pierre Aboulker 《Journal of Graph Theory》2014,75(4):311-322
A 4‐wheel is a graph formed by a cycle C and a vertex not in C that has at least four neighbors in C. We prove that a graph G that does not contain a 4‐wheel as a subgraph is 4‐colorable and we describe some structural properties of such a graph. 相似文献
19.
A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is L‐list 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 L‐list colorable for every list assignment with |L (v)| ≥ k for all v ∈ V, then G is said k‐choosable. A graph is said to be acyclically k‐choosable if the obtained coloring is acyclic. In this paper, we study the links between acyclic k‐choosability of G and Mad(G) defined as the maximum average degree of the subgraphs of G and give some observations about the relationship between acyclic coloring, choosability, and acyclic choosability. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 281–300, 2006 相似文献
20.
It is well known that every planar graph G is 2‐colorable in such a way that no 3‐cycle of G is monochromatic. In this paper, we prove that G has a 2‐coloring such that no cycle of length 3 or 4 is monochromatic. The complete graph K5 does not admit such a coloring. On the other hand, we extend the result to K5‐minor‐free graphs. There are planar graphs with the property that each of their 2‐colorings has a monochromatic cycle of length 3, 4, or 5. In this sense, our result is best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 25–38, 2004 相似文献