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.     

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 a matroid defined by ear-decompositions of graphs

A. Frank described in [1] an algorithm to determine the minimum number of edges in a graph G whose contraction leaves a factor-critical graph and he asked if there was an algorithm for the weighted version of the problem. We prove that the minimal critical-making edge-sets form the bases of a matroid and hence the matroid greedy algorithm gives rise to the desired algorithm.Partially supported by OTKA F014919, OTKA T17181 and OTKA T17580.     

Hadwiger's conjecture forK 6-free graphs

In 1943, Hadwiger made the conjecture that every loopless graph not contractible to the complete graph ont+1 vertices ist-colourable. Whent3 this is easy, and whent=4, Wagner's theorem of 1937 shows the conjecture to be equivalent to the four-colour conjecture (the 4CC). However, whent5 it has remained open. Here we show that whent=5 it is also equivalent to the 4CC. More precisely, we show (without assuming the 4CC) that every minimal counterexample to Hadwiger's conjecture whent=5 is apex, that is, it consists of a planar graph with one additional vertex. Consequently, the 4CC implies Hadwiger's conjecture whent=5, because it implies that apex graphs are 5-colourable.Research partially supported by NSF grants number DMS 8903132, and DMS 9103480 respectively. Both authors were also partially supported by the DIMACS Center at Rutgers University, and the research was carried out partially under a consulting agreement with Bellcore.     

Tutte sets in graphs II: The complexity of finding maximum Tutte sets

A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency. A subset X of V(G) for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. We explored the structural aspects of Tutte sets in another paper. Here, we consider the algorithmic complexity of finding Tutte sets in a graph. We first give two polynomial algorithms for finding a maximal Tutte set. We then consider the complexity of finding a maximum Tutte set, and show it is NP-hard for general graphs, as well as for several interesting restricted classes such as planar graphs. By contrast, we show we can find maximum Tutte sets in polynomial time for graphs of level 0 or 1, elementary graphs, and 1-tough graphs.     

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.     

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.     

Conservative weightings and ear-decompositions of graphs

A subsetJ of edges of a connected undirected graphG=(V, E) is called ajoin if |CJ||C|/2 for every circuitC ofG. Answering a question of P. Solé and Th. Zaslavsky, we derive a min-max formula for the maximum cardinality of a joint ofG. Namely, =(+|V|–1)/2 where denotes the minimum number of edges whose contraction leaves a factor-critical graph.To study these parameters we introduce a new decomposition ofG, interesting for its own sake, whose building blocks are factor-critical graphs and matching-covered bipartite graphs. We prove that the length of such a decomposition is always and show how an optimal join can be constructed as the union of perfect matchings in the building blocks. The proof relies on the Gallai-Edmonds structure theorem and gives rise to a polynomial time algorithm to construct the optima in question.     

2–3 graphs which have Vizing's adjacency property

2–3 graphs in which each vertex is adjacent to at least two vertices of degree 3 are shown to be characterised by the number of vertices of degree 3 adjacent to vertices of degree 3 only.     

Fractionally colouring total graphs

Bchzad and Vizing have conjectured that given any simple graph of maximum degree , one can colour its edges and vertices with +2 colours so that no two adjacent vertices, or two incident edges, or an edge and either of its ends receive the same colour. We show that for any simple graphG, V(G)E(G) can be fractionally coloured with +2 colours.     

Perfect couples of graphs

We generalize the concept of perfect graphs in terms of additivity of a functional called graph entropy. The latter is an information theoretic functional on a graphG with a probability distributionP on its vertex set. For any fixedP it is sub-additive with respect to graph union. The entropy of the complete graph equals the sum of those ofG and its complement G iffG is perfect. We generalize this recent result to characterize all the cases when the sub-additivity of graph entropy holds with equality.The research of the authors is partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant No. 1806 resp. No. 1812.     

More orthogonal double covers of complete graphs by Hamiltonian paths

An orthogonal double cover (ODC) of the complete graph K_n by a graph G is a collection G of n spanning subgraphs of K_n, all isomorphic to G, such that any two members of G share exactly one edge and every edge of K_n is contained in exactly two members of G. In the 1980s Hering posed the problem to decide the existence of an ODC for the case that G is an almost-Hamiltonian cycle, i.e. a cycle of length n-1. It is known that the existence of an ODC of K_n by a Hamiltonian path implies the existence of ODCs of K_4n and of K_16n, respectively, by almost-Hamiltonian cycles. Horton and Nonay introduced two-colorable ODCs and showed: If there are an ODC of K_n by a Hamiltonian path for some n?3 and a two-colorable ODC of K_q by a Hamiltonian path for some prime power q?5, then there is an ODC of K_qn by a Hamiltonian path. In [U. Leck, A class of 2-colorable orthogonal double covers of complete graphs by hamiltonian paths, Graphs Combin. 18 (2002) 155-167], two-colorable ODCs of K_n and K_2n, respectively, by Hamiltonian paths were constructed for all odd square numbers n?9. Here we continue this work and construct cyclic two-colorable ODCs of K_n and K_2n, respectively, by Hamiltonian paths for all n of the form n=4k²+1 or n=(k²+1)/2 for some integer k.     

The gallai-younger conjecture for planar graphs

Younger conjectured that for everyk there is ag(k) such that any digraphG withoutk vertex disjoint cycles contains a setX of at mostg(k) vertices such thatG–X has no directed cycles. Gallai had previously conjectured this result fork=1. We prove this conjecture for planar digraphs. Specifically, we show that ifG is a planar digraph withoutk vertex disjoint directed cycles, thenG contains a set of at mostO(klog(k)log(log(k))) vertices whose removal leaves an acyclic digraph. The work also suggests a conjecture concerning an extension of Vizing's Theorem for planar graphs.     

Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

Pfaffian graphs, <Emphasis Type="Italic">T</Emphasis>-joins and crossing numbers

We characterize Pfaffian graphs in terms of their drawings in the plane. We generalize the techniques used in the proof of this characterization, and prove a theorem about the numbers of crossings in T-joins in different drawings of a fixed graph. As a corollary we give a new proof of a theorem of Kleitman on the parity of crossings in drawings of K _2j+1 and K _2j+1,2k+1. Partially supported by NSF grants DMS-0200595 and DMS-0701033.     

A characterization of graphs with rank 4

The rank of a graph G is defined to be the rank of its adjacency matrix. In this paper, we consider the following problem: What is the structure of a connected graph with rank 4? This question has not yet been fully answered in the literature, and only some partial results are known. In this paper we resolve this question by completely characterizing graphs G whose adjacency matrix has rank 4.     

Two spectral characterizations of regular, bipartite graphs with five eigenvalues

Graphs with a few distinct eigenvalues usually possess an interesting combinatorial structure. We show that regular, bipartite graphs with at most six distinct eigenvalues have the property that each vertex belongs to the constant number of quadrangles. This enables to determine, from the spectrum alone, the feasible families of numbers of common neighbors for each vertex with other vertices in its part. For particular spectra, such as [6,2⁹,0⁶,-2⁹,-6] (where exponents denote eigenvalue multiplicities), there is a unique such family, which makes it possible to characterize all graphs with this spectrum.Using this lemma we also to show that, for r?2, a graph has spectrum if and only if it is a graph of a 1-resolvable transversal design TD(r,r), i.e., if it corresponds to the complete set of mutually orthogonal Latin squares of size r in a well-defined manner.     

Zero-divisor graphs of amalgamated duplication of a ring along an ideal

Let R be a commutative ring with identity and let I be an ideal of R. Let R?I be the subring of R×R consisting of the elements (r,r+i) for r∈R and i∈I. We study the diameter and girth of the zero-divisor graph of the ring R?I.     

Pfaffian labelings and signs of edge colorings

We relate signs of edge-colorings (as in classical Penrose’s result) with “Pfaffian labelings”, a generalization of Pfaffian orientations, whereby edges are labeled by elements of an Abelian group with an element of order two. In particular, we prove a conjecture of Goddyn that all k-edge-colorings of a k-regular Pfaffian graph G have the same sign. We characterize graphs that admit a Pfaffian labeling in terms of bricks and braces in their matching decomposition and in terms of their drawings in the projective plane. Partially supported by NSF grants 0200595 and 0354742.     

Some remarks on universal graphs

LetΓ be a class of countable graphs, and let ℱ(Γ) denote the class of all countable graphs that do not contain any subgraph isomorphic to a member ofΓ. Furthermore, letTΓ andHΓ denote the class of all subdivisions of graphs inΓ and the class of all graphs contracting to a member ofΓ, respectively. As the main result of this paper it is decided which of the classes ℱ(TK ⁿ ) and ℱ(HK ⁿ ),n≦ℵ₀, contain a universal element. In fact, for ℱ(TK ⁴)=ℱ(HK ⁴) a strongly universal graph is constructed, whereas for 5≦n≦ℵ₀ the classes ℱ(TK ⁿ ) and ℱ(HK ⁿ ) have no universal elements. Dedicated to Klaus Wagner on his 75^th birthday