共查询到20条相似文献,搜索用时 31 毫秒
1.
The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring. 相似文献
2.
Lovász, Saks, and Trotter showed that there exists an on-line algorithm which will color any on-linek-colorable graph onn vertices withO(nlog(2k–3)
n/log(2k–4)
n) colors. Vishwanathan showed that at least (log
k–1
n/k
k
) colors are needed. While these remain the best known bounds, they give a distressingly weak approximation of the number of colors required. In this article we study the case of perfect graphs. We prove that there exists an on-line algorithm which will color any on-linek-colorable perfect graph onn vertices withn
10k/loglogn
colors and that Vishwanathan's techniques can be slightly modified to show that his lower bound also holds for perfect graphs. This suggests that Vishwanathan's lower bound is far from tight in the general case.Research partially supported by Office of Naval Research grant N00014-90-J-1206. 相似文献
3.
《Journal of Algorithms in Cognition, Informatics and Logic》1988,9(1):63-82
We describe a simple and efficient heuristic algorithm for the graph coloring problem and show that for all k ≥ 1, it finds an optimal coloring for almost all k-colorable graphs. We also show that an algorithm proposed by Brélaz and justified on experimental grounds optimally colors almost all k-colorable graphs. Efficient implementations of both algorithms are given. The first one runs in O(n + m log k) time where n is the number of vertices and m the number of edges. The new implementation of Brélaz's algorithm runs in O(m log n) time. We observe that the popular greedy heuristic works poorly on k-colorable graphs. 相似文献
4.
A graph is (k, d)-colorable if one can color the vertices with k colors such that no vertex is adjacent to more than d vertices of its same color. In this paper we investigate the existence of such colorings in surfaces and the complexity of coloring problems. It is shown that a toroidal graph is (3, 2)- and (5, 1)-colorable, and that a graph of genus γ is (χγ/(d + 1) + 4, d)-colorable, where χγ is the maximum chromatic number of a graph embeddable on the surface of genus γ. It is shown that the (2, k)-coloring, for k ≥ 1, and the (3, 1)-coloring problems are NP-complete even for planar graphs. In general graphs (k, d)-coloring is NP-complete for k ≥ 3, d ≥ 0. The tightness is considered. Also, generalizations to defects of several algorithms for approximate (proper) coloring are presented. © 1997 John Wiley & Sons, Inc. 相似文献
5.
We call a graph (m, k)-colorable if its vertices can be colored with m colors in such a way that each vertex is adjacent to at most k vertices of the same color as itself. For the class of planar graphs, and the class of outerplanar graphs, we determine all pairs (m, k) such that every graph in the class is (m, k)-colorable. We include an elementary proof (not assuming the truth of the four-color theorem) that every planar graph is (4, 1)-colorable. Finally, we prove that, for each compact surface S, there is an integer k = k(S) such that every graph in S can be (4, k)-colored; we conjecture that 4 can be replaced by 3 in this statement. 相似文献
6.
We study the problem of coloring graphs in an online manner. The only known deterministic online graph coloring algorithm with a sublinear performance function was found by [9.], 319–325). Their algorithm colors graphs of chromatic number χ with no more than (2χn)/log* n colors, where n is the number of vertices. They point out that the performance can be improved slightly for graphs with bounded chromatic number. For three-chromatic graphs the number of colors used, for example, is O(n log log log n/log log n). We show that randomization helps in coloring graphs online. We present a simple randomized online algorithm to color graphs with expected number of colors O(2χχ2n(χ−2)/(χ−1)(log n)1/(χ−1)). For three-colorable graphs the expected number of colors our algorithm uses is
. All our algorithms run in polynomial time. It is interesting to note that our algorithm compares well with the best known polynomial time offline algorithms. For instance, the best polynomial time algorithm known for three-colorable graphs, due to [4.] pp. 554–562). We also prove a lower bound of Ω((1/(χ − 1))((log n/(12(χ + 1))) − 1)χ−1) for the randomized model. No lower bound for the randomized model was previously known. For bounded χ, our result improves even the best known lower bound for the deterministic case: Ω((log n/log log n)χ−1), due to Noga Alon (personal communication, September 1989). 相似文献
7.
H. A. Kierstead 《Israel Journal of Mathematics》1998,105(1):93-104
We show that for anyk, there exists an on-line algorithm that will color anyk-colorable graph onn vertices withO(n
1−1/k!
) colors. This improves the previous best upper bound ofO(nlog(2k−3)
n/log(2k−4)
n) due to Lovász, Saks, and Trotter. In the special casesk=3 andk=4 we obtain on-line algorithms that useO(n
2/3log1/3
n) andO(n
5/6log1/6
n) colors, respectively. 相似文献
8.
Perfect matchings of k-Pfaffian graphs may be enumerated in polynomial time on the number of vertices, for fixed k. In general, this enumeration problem is #P-complete. We give a Composition Theorem of 2r-Pfaffian graphs from r Pfaffian spanning subgraphs. Constructions of k-Pfaffian graphs known prior to this seem to be of a very different and essentially topological nature. We apply our Composition Theorem to produce a bipartite graph on 10 vertices that is 6-Pfaffian but not 4-Pfaffian. This is a counter-example to a conjecture of Norine (2009) [8], which states that the Pfaffian number of a graph is a power of four. 相似文献
9.
Guillermo Durán Min Chih Lin Sergio Mera Jayme Luiz Szwarcfiter 《Discrete Applied Mathematics》2006,154(13):1783-1790
A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a -free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n2). These algorithms suppose that an HCA model of the graph is given. 相似文献
10.
We describe a new algorithm, the (k, ℓ)-pebble game with colors, and use it to obtain a characterization of the family of (k, ℓ)-sparse graphs and algorithmic solutions to a family of problems concerning tree decompositions of graphs. Special instances
of sparse graphs appear in rigidity theory and have received increased attention in recent years. In particular, our colored
pebbles generalize and strengthen the previous results of Lee and Streinu [12] and give a new proof of the Tutte-Nash-Williams
characterization of arboricity. We also present a new decomposition that certifies sparsity based on the (k, ℓ)-pebble game with colors. Our work also exposes connections between pebble game algorithms and previous sparse graph algorithms
by Gabow [5], Gabow and Westermann [6] and Hendrickson [9].
Ileana Streinu; Research of both authors funded by the NSF under grants NSF CCF-0430990 and NSF-DARPA CARGO CCR-0310661 to
the first author. 相似文献
11.
Manu Basavaraju 《Discrete Mathematics》2008,308(24):6650-6653
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 it is denoted by a′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors. 相似文献
12.
Dennis P. Geller 《Discrete Mathematics》1976,16(1):9-12
An r-tuple coloring of a graph is one in which r colors are assigned to each point of the graph so that the sets of colors assigned to adjacent points are always disjoint. We investigate the question of whether a uniquely n-colorable graph can receive an r-tuple coloring with fewer than nr colors. We show that this cannot happen for n=3 and r=2 and that for a given n and r to establish the conjecture that no uniquely n-colorable graph can receive an r-tuple coloring from fewer than nr colors it suffices to prove it for on a finite set of uniquely n-colorable graphs. 相似文献
13.
We prove that coloring a 3-uniform 2-colorable hypergraph with c colors is NP-hard for any constant c. The best known algorithm [20] colors such a graph using O(n1/5) colors. Our result immediately implies that for any constants k ≥ 3 and c2 > c1 > 1, coloring a k-uniform c1-colorable hypergraph with c2 colors is NP-hard; the case k = 2, however, remains wide open.
This is the first hardness result for approximately-coloring a 3-uniform hypergraph that is colorable with a constant number
of colors. For k ≥ 4 such a result has been shown by [14], who also discussed the inherent difference between the k = 3 case and k ≥ 4.
Our proof presents a new connection between the Long-Code and the Kneser graph, and relies on the high chromatic numbers of
the Kneser graph [19,22] and the Schrijver graph [26]. We prove a certain maximization variant of the Kneser conjecture, namely
that any coloring of the Kneser graph by fewer colors than its chromatic number, has ‘many’ non-monochromatic edges.
* Research supported by NSF grant CCR-9987845.
† Supported by an Alon Fellowship and by NSF grant CCR-9987845.
‡ Work supported in part by NSF grants CCF-9988526 and DMS 9729992, and the State of New Jersery. 相似文献
14.
Jesper Makholm Byskov Bolette Ammitzbll Madsen Bjarke Skjernaa 《Journal of Graph Theory》2005,48(2):127-132
We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105n/10 ≈ 1.5926n; such subgraphs show an upper bound of O(12n/4) = O(1.8613n) and give an algorithm that finds all maximal induced bipartite subgraphs in time within a polynomial factor of this bound. This algorithm is used in the construction of algorithms for checking k‐colorability of a graph. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 127–132, 2005 相似文献
15.
In this article we investigate properties of the class of all l-colorable graphs on n vertices, where l = l(n) may depend on n. Let Gln denote a uniformly chosen element of this class, i.e., a random l-colorable graph. For a random graph Gln we study in particular the property of being uniquely l-colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l-colorable graphs on n vertices with m = m(n) edges. 相似文献
16.
A plane graph G is edge-face k-colorable if its edges and faces can be colored with k colors such that any two adjacent or incident elements receive different colors. It is known that every plane graph G of maximum degree Δ ≥ 8 is edge-face (Δ + 1)-colorable. The condition Δ ≥ 8 is improved to Δ ≥ 7 in this paper. 相似文献
17.
Christine T. Cheng 《Discrete Mathematics》2009,309(16):5169-434
A vertex k-coloring of graph G is distinguishing if the only automorphism of G that preserves the colors is the identity map. It is proper-distinguishing if the coloring is both proper and distinguishing. The distinguishing number ofG, D(G), is the smallest integer k so that G has a distinguishing k-coloring; the distinguishing chromatic number ofG, χD(G), is defined similarly.It has been shown recently that the distinguishing number of a planar graph can be determined efficiently by counting a related parameter-the number of inequivalent distinguishing colorings of the graph. In this paper, we demonstrate that the same technique can be used to compute the distinguishing number and the distinguishing chromatic number of an interval graph. We make use of PQ-trees, a classic data structure that has been used to recognize and test the isomorphism of interval graphs; our algorithms run in O(n3log3n) time for graphs with n vertices. We also prove a number of results regarding the computational complexity of determining a graph’s distinguishing chromatic number. 相似文献
18.
We answer some of the questions raised by Golumbic, Lipshteyn and Stern and obtain some other results about edge intersection graphs of paths on a grid (EPG graphs). We show that for any d≥4, in order to represent every n vertex graph with maximum degree d as an edge intersection graph of n paths on a grid, a grid of area Θ(n2) is needed. We also show several results related to the classes Bk-EPG, where Bk-EPG denotes the class of graphs that have an EPG representation such that each path has at most k bends. In particular, we prove: For a fixed k and a sufficiently large n, the complete bipartite graph Km,n does not belong to B2m−3-EPG (it is known that this graph belongs to B2m−2-EPG); for any odd integer k we have Bk-EPG Bk+1-EPG; there is no number k such that all graphs belong to Bk-EPG; only 2O(knlog(kn)) out of all the labeled graphs with n vertices are in Bk-EPG. 相似文献
19.
An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable coloring of a graph G with k colors is said to be the equitable chromatic number of G and is denoted by χ=(G). The least positive integer k such that for any k′ ≥ k there exists an equitable coloring of a graph G with k′ colors is said to be the equitable chromatic threshold of G and is denoted by χ=*(G). In this paper, we investigate the asymptotic behavior of these coloring parameters in the probability space G(n,p) of random graphs. We prove that if n?1/5+? < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ=(G(n,p)) = (1 + o(1))χ(G(n,p)) holds (where χ(G(n,p)) is the ordinary chromatic number of G(n,p)). We also show that there exists a constant C such that if C/n < p < 0.99, then almost surely χ(G(n,p)) ≤ χ=(G(n,p)) ≤ (2 + o(1))χ(G(n,p)). Concerning the equitable chromatic threshold, we prove that if n?(1??) < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ=* (G(n,p)) ≤ (2 + o(1))χ(G(n,p)) holds, and if < p < 0.99 for some 0 < ?, then almost surely we have χ(G(n,p)) ≤ χ=*(G(n,p)) = O?(χ(G(n,p))). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 相似文献
20.
Tom Rackham 《Journal of Graph Theory》2011,68(2):129-136
A (k, 1)‐coloring of a graph is a vertex‐coloring with k colors such that each vertex is permitted at most 1 neighbor of the same color. We show that every planar graph has at least cρn distinct (4, 1)‐colorings, where c is constant and ρ≈1.466 satisfies ρ3 = ρ2 + 1. On the other hand for any ε>0, we give examples of planar graphs with fewer than c(? + ε)n distinct (4, 1)‐colorings, where c is constant and . Let γ(S) denote the chromatic number of a surface S. For every surface S except the sphere, we show that there exists a constant c′ = c′(S)>0 such that every graph embeddable in S has at least c′2n distinct (γ(S), 1)‐colorings. © 2010 Wiley Periodicals, Inc. J Graph Theory 28:129‐136, 2011 相似文献