共查询到20条相似文献,搜索用时 31 毫秒
1.
A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F, a certain “greedy” coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time. 相似文献
2.
We consider the class of graphs where every induced subgraph possesses a vertex whose neighborhood has no P4 and no 2K2. We prove that Berge's Strong Perfect Graph Conjecture holds for such graphs. The class generalizes several well-known families of perfect graphs, such as triangulated graphs and bipartite graphs. Testing membership in this class and computing the maximum clique size for a graph in this class is not hard, but finding an optimal coloring is NP-hard. We give a polynomial-time algorithm for optimally coloring the vertices of such a graph when it is perfect. © 1996 John Wiley & Sons, Inc. 相似文献
3.
A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph G is the largest integer k such that G admits a b‐coloring with k colors. A graph is b‐perfect if the b‐chromatic number is equal to the chromatic number for every induced subgraph of G. We prove that a graph is b‐perfect if and only if it does not contain as an induced subgraph a member of a certain list of 22 graphs. This entails the existence of a polynomial‐time recognition algorithm and of a polynomial‐time algorithm for coloring exactly the vertices of every b‐perfect graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:95–122, 2012 相似文献
4.
The pre-coloring extension problem consists, given a graph G and a set of nodes to which some colors are already assigned, in finding a coloring of G with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem
on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs. We answer
a question of Hujter and Tuza by showing that “PrExt perfect” graphs are exactly the co-Meyniel graphs, which also generalizes
results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph
belongs to a restricted class of perfect graphs (“co-Artemis” graphs, which are “co-perfectly contractile” graphs), whose
perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still
depends on the ellipsoid method for coloring perfect graphs.
C.N.R.S.
Final version received: January, 2007 相似文献
5.
A graph is a strict-quasi parity (SQP) graph if every induced subgraph that is not a clique contains a pair of vertices with
no odd chordless path between them (an “even pair”). We present an O(n
3) algorithm for recognizing planar strict quasi-parity graphs, based on Wen-Lian Hsu's decomposition of planar (perfect) graphs
and on the (non-algorithmic) characterization of planar minimal non-SQP graphs given in [9].
Received: September 21, 1998 Final version received: May 9, 2000 相似文献
6.
S. A. Puzynina 《Siberian Mathematical Journal》2011,52(1):91-104
A coloring of vertices of a graph G is called r-perfect, if the color structure of each ball of radius r in G depends only on the color of the center of the ball. The parameters of a perfect coloring are given by the matrix A = (a
ij
)
i,j=1
n
, where n is the number of colors and a
ij
is the number of vertices of color j in a ball centered at a vertex of color i. We study the periodicity of perfect colorings of the graphs of the infinite hexagonal and triangular grids. We prove that
for every 1-perfect coloring of the infinite triangular and every 1- and 2-perfect coloring of the infinite hexagonal grid
there exists a periodic perfect coloring with the same matrix. The periodicity of perfect colorings of big radii have been
studied earlier. 相似文献
7.
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). 相似文献
8.
In (strongly) perfect graphs, we define (strongly) canonical colorings; we show that for some classes of graphs, such colorings
can be obtained by sequential coloring techniques.
Chromatic properties ofP
4-free graphs based on such coloring techniques are mentioned and extensions to graphs containing no inducedP
5,
orC
5 are presented. In particular we characterize the class of graphs in which any maximal (or minimal) nodex in the vicinal preorder has the following property: there is either noP
4 havingx as a midpoint or noP
4 havingx as an endpoint. For such graphs, according to a result of Chvatal, there is a simple sequential coloring algorithm. 相似文献
9.
W. -L. Hsu 《Combinatorica》1986,6(4):381-385
This paper describes a decomposition scheme for coloring perfect graphs. Based on this scheme, one need only concentrate on
coloring highly connected (at least 3-connected) perfect graphs. This idea is illustrated on planar perfect graphs, which
yields a straightforward coloring algorithm. We suspect that, under appropriate definition, highly connected perfect graphs
might possess certain regular properties that are amenable to coloring algorithms.
This research has been supported in part by National Science Foundation under grant ECS—8105989 to Northwestern University. 相似文献
10.
The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that if G is a connected claw‐free circular‐perfect graph with χ(G)>ω(G), then min{α(G), ω(G)}=2. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw‐free circular‐perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{α(G), ω(G)}=2. In contrast to this result, it is shown in Z. Pan and X. Zhu [European J Combin 29(4) (2008), 1055–1063] that minimal circular‐imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. In this article, we prove that claw‐free minimal circular‐imperfect graphs G have min{α(G), ω(G)}≤3. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 163–172, 2010 相似文献
11.
We color the nodes of a graph by first applying successive contractions to non-adjacent nodes until we get a clique; then we color the clique and decontract the graph. We show that this algorithm provides a minimum coloring and a maximum clique for any Meyniel graph by using a simple rule for choosing which nodes are to be contracted. This O(n3) algorithm is much simpler than those already existing for Meyniel graphs. Moreover, the optimality of this algorithm for Meyniel graphs provides an alternate nice proof of the following result of Hoàng: a graph G is Meyniel if and only if, for any induced subgraph of G, each node belongs to a stable set that meets all maximal cliques. Finally we give a new characterization for Meyniel graphs. 相似文献
12.
Michel Vasquez 《Journal of Heuristics》2004,10(4):407-413
For the Queens_n
2 graph coloring problems no chromatic numbers are available for n > 9 except where n is not a multiple of 2 or 3. In this paper we propose an exact algorithm that takes advantage of the particular structure of these graphs. The algorithm works on the independent sets of the graph rather than on the vertices to be colored. It combines branch and bound, for independent set assignment, with a clique based filtering procedure. A first experimentation of this approach provided the coloring number values ranging for n = 10 to n = 14. 相似文献
13.
David Dfossez 《Journal of Graph Theory》2006,53(3):233-249
We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K4‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006 相似文献
14.
Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete (Hoàng in SIAM J Discret Math 23:2156–2162,
2010). We show that whether a building-free graph contains a sun can be decided in O(min{mn
3, m
1.5
n
2}) time and, if a sun exists, it can be found in the same time bound. The class of building-free graphs contains many interesting
classes of perfect graphs such as Meyniel graphs which, in turn, contains classes such as hhd-free graphs, i-triangulated
graphs, and parity graphs. Moreover, there are imperfect graphs that are building-free. The class of building-free graphs
generalizes several classes of graphs for which an efficient test for the presence of a sun is known. We also present a vertex
elimination scheme for the class of (building, gem)-free graphs. The class of (building, gem)-free graphs is a generalization
of the class of distance hereditary graphs and a restriction of the class of (building, sun)-free graphs. 相似文献
15.
S. V. Avgustinovich I. Yu. Mogil’nykh 《Journal of Applied and Industrial Mathematics》2011,5(1):19-30
In this article the parameter matrices are enumerated of all perfect 2-colorings of the Johnson graphs J(8, 3) and J(8, 4), and several constructions are presented for perfect 2-coloring of J(2w, w) and J(2m, 3). The concept of a perfect coloring generalizes the concept of completely regular code introduced by P. Delsarte. The
problem of existence of similar structures in Johnson graphs is closely related to the problem of existence of completely
regular codes in Johnson graphs and, in particular, to the Delsarte conjecture on the nonexistence of nontrivial perfect codes
in Johnson graphs, the problem of existence of block designs, and other well-known problems. 相似文献
16.
Many classes of graphs where the vertex coloring problem is polynomially solvable are known, the most prominent being the
class of perfect graphs. However, the list-coloring problem is NP-complete for many subclasses of perfect graphs. In this
work we explore the complexity boundary between vertex coloring and list-coloring on such subclasses of perfect graphs where
the former admits polynomial-time algorithms but the latter is NP-complete. Our goal is to analyze the computational complexity
of coloring problems lying “between” (from a computational complexity viewpoint) these two problems: precoloring extension,
μ-coloring, and (γ,μ)-coloring.
Flavia Bonomo partially supported by UBACyT Grants X606 and X069 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4
(Brazil).
Guillermo Durán partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems”
(Chile), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil).
Javier Marenco partially supported by UBACyT Grant X069 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). 相似文献
17.
Olivier Durand de Gevigney Fr��d��ric Meunier Christian Popa Julien Reygner Ayrin Romero 《4OR: A Quarterly Journal of Operations Research》2011,9(2):175-188
Let T = (V, A) be a directed tree. Given a collection P{\mathcal{P}} of dipaths on T, we can look at the arc-intersection graph I(P,T){I(\mathcal{P},T)} whose vertex set is P{\mathcal{P}} and where two vertices are connected by an edge if the corresponding dipaths share a common arc. Monma and Wei, who started
their study in a seminal paper on intersection graphs of paths on a tree, called them DE graphs (for directed edge path graphs)
and proved that they are perfect. DE graphs find one of their applications in the context of optical networks. For instance,
assigning wavelengths to set of dipaths in a directed tree network consists in finding a proper coloring of the arc-intersection
graph. In the present paper, we give
– |
a simple algorithm finding a minimum proper coloring of the paths. 相似文献
18.
Denis S. Krotov 《Designs, Codes and Cryptography》2011,61(3):315-329
A vertex coloring of a graph is called “perfect” if for any two colors a and b, the number of the color-b neighbors of a color-a vertex x does not depend on the choice of x, that is, depends only on a and b (the corresponding partition of the vertex set is known as “equitable”). A set of vertices is called “completely regular”
if the coloring according to the distance from this set is perfect. By the “weight distribution” of some coloring with respect
to some set we mean the information about the number of vertices of every color at every distance from the set. We study the
weight distribution of a perfect coloring (equitable partition) of a graph with respect to a completely regular set (in particular,
with respect to a vertex if the graph is distance-regular). We show how to compute this distribution by the knowledge of the
color composition over the set. For some partial cases of completely regular sets, we derive explicit formulas of weight distributions.
Since any (other) completely regular set itself generates a perfect coloring, this gives universal formulas for calculating
the weight distribution of any completely regular set from its parameters. In the case of Hamming graphs, we prove a very
simple formula for the weight enumerator of an arbitrary perfect coloring. 相似文献
19.
Kishore Yadav Satish Varagani Kishore Kothapalli V.Ch. Venkaiah 《Discrete Mathematics》2011,311(5):748
An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted a(G), is the minimum number of colors required for acyclic vertex coloring of graph G. For a family F of graphs, the acyclic chromatic number of F, denoted by a(F), is defined as the maximum a(G) over all the graphs G∈F. In this paper we show that a(F)=8 where F is the family of graphs of maximum degree 5 and give a linear time algorithm to achieve this bound. 相似文献
20.
Alan Tucker 《Discrete Mathematics》1983,44(2):187-194
This paper defines the concept of sequential coloring. If G or its complement is one of four major types of perfect graphs, G is shown to be uniquely k-colorable it and only if it is sequentially k-colorable. It is conjectured that this equivalence is true for all perfect graphs. A potential role for sequential coloring in verifying the Strong Perfect Graph Conjecture is discussed. This conjecture is shown to be true for strongly sequentially colorable graphs. 相似文献
|