On kernels in perfect graphs

A kernel of a digraphD is a set of vertices which is both independent and absorbant. In 1983, C. Berge and P. Duchet conjectured that an undirected graphG is perfect if and only if the following condition is fulfilled: ifD is an orientation ofG (where pairs of opposite arcs are allowed) and if every clique ofD has a kernel thenD has a kernel. We prove here the conjecture for the complements of strongly perfect graphs and establish that a minimal counterexample to the conjecture is not a complete join of an independent set with another graph.     

Coloring planar perfect graphs by decomposition

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.     

A note on perfect graphs

Let the lines of a complete graph be 3-colored so that no triangle gets 3 different colors. If two of these colors form perfect graphs then so does the third.     

On-line coloring of perfect graphs

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.     

Counting perfect matchings in n-extendable graphs

The structural theory of matchings is used to establish lower bounds on the number of perfect matchings in n-extendable graphs. It is shown that any such graph on p vertices and q edges contains at least ⌈(n+1)!/4[q-p-(n-1)(2Δ-3)+4]⌉ different perfect matchings, where Δ is the maximum degree of a vertex in G.     

Radius-edge-invariant and diameter-edge-invariant graphs

The eccentricity e(v) of v is the distance to a farthest vertex from v. The radius r(G) is the minimum eccentricity among the vertices of G and the diameter d(G) is the maximum eccentricity. For graph G−e obtained by deleting edge e in G, we have r(G−e)?r(G) and d(G−e)?d(G). If for all e in G, r(G−e)=r(G), then G is radius-edge-invariant. Similarly, if for all e in G, d(G−e)=d(G), then G is diameter-edge-invariant. In this paper, we study radius-edge-invariant and diameter-edge-invariant graphs and obtain characterizations of radius-edge-invariant graphs and diameter-edge-invariant graphs of diameter two.     

Diperfect graphs

Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ₁, μ₂, ..., μ_k such tht |μ_i ∩S|=1 for alli. Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic number; here again, we do not know if there exists an optimal coloring (S ₁,S ₂, ...,S _k) and a path μ such that |μ ∩S _i|=1 for alli. In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the perfect graph conjecture. Dedicated to Tibor Gallai on his seventieth birthday     

The new methods for constructing matching-equivalence graphs

Two graphs G and H with order n are said to be matching-equivalent if and only if the number of r-matchings (i.e., the number of ways in which r disjoint edges can be chosen) is the same for each of the graphs G and H for each r, where 0?r?n. In this paper, the new methods for constructing ‘matching-equivalent’ graphs are given, and some families of non-matching unique graphs are also obtained.     

Unit-distance graphs,graphs on the integer lattice and a Ramsey type result

Summary Let (R ², 1) denote the graph withR ² as the vertex set and two vertices adjacent if and only if their Euclidean distance is 1. The problem of determining the chromatic number(R ², 1) is still open; however,(R ², 1) is known to be between 4 and 7. By a theorem of de Bruijn and Erdös, it is enough to consider only finite subgraphs of (R ², 1). By a recent theorem of Chilakamarri, it is enough to consider certain graphs on the integer lattice. More precisely, forr > 0, let (Z ²,r, ) denote a graph with vertex setZ ² and two vertices adjacent if and only if their Euclidean distance is in the closed interval [r – ,r + ]. A simple graph is faithfully -recurring inZ ² if there exists a real numberd > 0 such that, for arbitrarily larger, G is isomorphic to a subgraph of (Z ²,r, ) in which every pair of vertices are at least distancedr apart. Chilakamarri has shown that, ifG is a finite simple graph, thenG is isomorphic to a subgraph of (R ², 1) if and only ifG is faithfully -recurring inZ ². In this paper we prove that(Z ²,r, ) 5 for integersr 1. We also prove a Ramsey type result which states that for any integerr > 1, and any coloring ofZ ² either there exists a monochromatic pair of vertices with their distance in the closed interval [r – ,r + ] or there exists a set of three vertices closest to each other with three distinct colors.     

Colorings and orientations of graphs

Bounds for the chromatic number and for some related parameters of a graph are obtained by applying algebraic techniques. In particular, the following result is proved: IfG is a directed graph with maximum outdegreed, and if the number of Eulerian subgraphs ofG with an even number of edges differs from the number of Eulerian subgraphs with an odd number of edges then for any assignment of a setS(v) ofd+1 colors for each vertexv ofG there is a legal vertex-coloring ofG assigning to each vertexv a color fromS(v).Research supported in part by a United States-Israel BSF Grant and by a Bergmann Memorial Grant.     

Entropy bounds for perfect matchings and Hamiltonian cycles

For a graph G = (V,E) and x: E → ℜ⁺ satisfying Σ _e∋υ x _e = 1 for each υ ∈ V, set h(x) = Σ _e x _e log(1/x _e ) (with log = log₂). We show that for any n-vertex G, random (not necessarily uniform) perfect matching f satisfying a mild technical condition, and x _e =Pr(e∈f),

On unimodular graphs

We study graphs whose adjacency matrices have determinant equal to 1 or −1, and characterize certain subclasses of these graphs. Graphs whose adjacency matrices are totally unimodular are also characterized. For bipartite graphs having a unique perfect matching, we provide a formula for the inverse of the corresponding adjacency matrix, and address the problem of when that inverse is diagonally similar to a nonnegative matrix. Special attention is paid to the case that such a graph is unicyclic.     

Preperfect graphs

We say that a vertexx of a graph is predominant if there exists another vertexy ofG such that either every maximum clique ofG containingy containsx or every maximum stable set containingx containsy. A graph is then called preperfect if every induced subgraph has a predominant vertex. We show that preperfect graphs are perfect, and that several well-known classes of perfect graphs are preperfect. We also derive a new characterization of perfect graphs.     

Colouring series-parallel graphs

We establish a minimax formula for the chromatic index of series-parallel graphs; and also prove the correctness of a greedy algorithm for finding a vertex-colouring of a series-parallel graph.     

On the index of tricyclic graphs with perfect matchings

Let T(2k) be the set of all tricyclic graphs on 2k(k?2) vertices with perfect matchings. In this paper, we discuss some properties of the connected graphs with perfect matchings, and then determine graphs with the largest index in T(2k).     

Heterochromatic tree partition numbers for complete bipartite graphs

An r-edge-coloring of a graph G is a surjective assignment of r colors to the edges of G. A heterochromatic tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by t_r(G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we give an explicit formula for the heterochromatic tree partition number of an r-edge-colored complete bipartite graph K_m,n.     

On thefg-coloring of graphs

This paper introduces a new type of edge-coloring of multigraphs, called anfg-coloring, in which each color appears at each vertexv no more thanf(v) times and at each set of multiple edges joining verticesv andw no more thang(vw) times. The minimum number of colors needed tofg-color a multigraphG is called thefg-chromatic index ofG. Various upper bounds are given on thefg-chromatic index. One of them is a generalization of Vizing's bound for the ordinary chromatic index. Our proof is constructive, and immediately yields a polynomial-time algorithm tofg-color a given multigraph using colors no more than twice thefg-chromatic index.     

Subgraphs of colour-critical graphs

Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed. In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc _k n ² edges must be removed. In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph.     

Independent sets ink-chromatic graphs

A graph is said to have propertyP _k if in eachk-colouring ofG using allk colours there arek independent vertices having all colours. An (unpublished) suggestion of P. Erdős is answered in the affirmative: For eachk≧3 there is a k-critical graph withP _k . With the aid of a construction of T. Gallaik-chromatic graphs (k≧7) withP _k orP _k+1 of arbitrarily high connectivity are obtained. The main result is: Eachk-chromatic graph (k≧3) of girth ≧6 hasP _k or is a circuit of length 7. Dedicated to Paul Erdős on his seventieth birthday     

r-Strong edge colorings of graphs

Let G be a graph and for any natural number r, denotes the minimum number of colors required for a proper edge coloring of G in which no two vertices with distance at most r are incident to edges colored with the same set of colors. In [Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626] it has been proved that for any tree T with at least three vertices, . Here we generalize this result and show that . Moreover, we show that if for any two vertices u and v with maximum degree d(u,v)?3, then . Also for any tree T with Δ(T)?3 we prove that . Finally, it is shown that for any graph G with no isolated edges, .