Highly parity linked graphs

A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x ₁,x ₂, …, x _k ,y ₁,y ₂, …, y _k , G contains k pairwise disjoint paths P ₁, …, P _k such that P _i joins x _i and y _i for i = 1,2, …, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P ₁, …, P _k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph. In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the Erdős-Pósa type result for parity-k-linked graphs. Research partly supported by the Japan Society for the Promotion of Science for Young Scientists, by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research and by Inoue Research Award for Young Scientists.     

Arc-disjoint in-trees in directed graphs

Given a directed graph D = (V,A) with a set of d specified vertices S = {s ₁,…, s _d } ⊆ V and a function f: S → ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition such that there exist Σ _i=1 ^d f(s _i ) arc-disjoint in-trees denoted by T _i,1,T _i,2,…, for every i = 1,…,d such that T _i,1,…, are rooted at s _i and each T _i,j spans the vertices from which s _i is reachable. This generalizes the result of Edmonds [2], i.e., the necessary and sufficient condition that for a directed graph D=(V,A) with a specified vertex s∈V, there are k arc-disjoint in-trees rooted at s each of which spans V. Furthermore, we extend another characterization of packing in-trees of Edmonds [1] to the one in our case. Supported by JSPS Research Fellowships for Young Scientists. Supported by the project New Horizons in Computing, Grand-in-Aid for Scientific Research on Priority Areas, MEXT Japan.     

On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary

It is shown that both the undirected and the directed edge-disjoint paths problem are NP-complete, if the supply graph is planar and all edges of the demand graph are incident with vertices lying on the outer boundary of the supply graph. In the directed case, the problem remains NP-complete, if in addition the supply graph is acyclic. The undirected case solves open problem no. 56 of A. Schrijver’s book Combinatorial Optimization.     

Note on limits of finite graphs

We prove that for any weakly convergent sequence of finite graphs with bounded vertex degrees, there exists a topological limit graphing.     

Independent systems of representatives in weighted graphs

The following conjecture may have never been explicitly stated, but seems to have been floating around: if the vertex set of a graph with maximal degree Δ is partitioned into sets V _i of size 2Δ, then there exists a coloring of the graph by 2Δ colors, where each color class meets each V _i at precisely one vertex. We shall name it the strong 2Δ-colorability conjecture. We prove a fractional version of this conjecture. For this purpose, we prove a weighted generalization of a theorem of Haxell, on independent systems of representatives (ISR’s). En route, we give a survey of some recent developments in the theory of ISR’s. The research of the first author was supported by grant no 780/04 from the Israel Science Foundation, and grants from the M. & M. L. Bank Mathematics Research Fund and the fund for the promotion of research at the Technion. The research of the third author was supported by the Sacta-Rashi Foundation.     

Connected but not path-connected subspaces of infinite graphs

Solving a problem of Diestel [9] relevant to the theory of cycle spaces of infinite graphs, we show that the Freudenthal compactification of a locally finite graph can have connected subsets that are not path-connected. However we prove that connectedness and path-connectedness to coincide for all but a few sets, which have a complicated structure.     

Colored graphs without colorful cycles

A colored graph is a complete graph in which a color has been assigned to each edge, and a colorful cycle is a cycle in which each edge has a different color. We first show that a colored graph lacks colorful cycles iff it is Gallai, i.e., lacks colorful triangles. We then show that, under the operation mon ≡ m + n − 2, the omitted lengths of colorful cycles in a colored graph form a monoid isomorphic to a submonoid of the natural numbers which contains all integers past some point. We prove that several but not all such monoids are realized. We then characterize exact Gallai graphs, i.e., graphs in which every triangle has edges of exactly two colors. We show that these are precisely the graphs which can be iteratively built up from three simple colored graphs, having 2, 4, and 5 vertices, respectively. We then characterize in two different ways the monochromes, i.e., the connected components of maximal monochromatic subgraphs, of exact Gallai graphs. The first characterization is in terms of their reduced form, a notion which hinges on the important idea of a full homomorphism. The second characterization is by means of a homomorphism duality. The first author would like to express his thanks for support by project LN 00A056 of the Ministry of Education of the Czech Republic. The second author would like to express his thanks for support by project LN 00A056 of the Ministry of Education of the Czech Republic, by the NSERC of Canada and by the Gudder Trust of the University of Denver.     

Total domination of graphs and small transversals of hypergraphs

The main result of this paper is that every 4-uniform hypergraph on n vertices and m edges has a transversal with no more than (5n + 4m)/21 vertices. In the particular case n = m, the transversal has at most 3n/7 vertices, and this bound is sharp in the complement of the Fano plane. Chvátal and McDiarmid [5] proved that every 3-uniform hypergraph with n vertices and edges has a transversal of size n/2. Two direct corollaries of these results are that every graph with minimal degree at least 3 has total domination number at most n/2 and every graph with minimal degree at least 4 has total domination number at most 3n/7. These two bounds are sharp.     

Coloring even-faced graphs in the torus and the Klein bottle

We prove that a triangle-free graph drawn in the torus with all faces bounded by even walks is 3-colorable if and only if it has no subgraph isomorphic to the Cayley graph C(Z ₁₃; 1,5). We also prove that a non-bipartite quadrangulation of the Klein bottle is 3-colorable if and only if it has no non-contractible separating cycle of length at most four and no odd walk homotopic to a non-contractible two-sided simple closed curve. These results settle a conjecture of Thomassen and two conjectures of Archdeacon, Hutchinson, Nakamoto, Negami and Ota. Institute for Theoretical Computer Science is supported as project 1M0545 by the Ministry of Education of the Czech Republic. The author was visiting Georgia Institute of Technology as a Fulbright scholar in the academic year 2005/06. Partially supported by NSF Grants No. DMS-0200595 and DMS-0354742.     

Partitions of large Rado graphs

Let κ be a cardinal which is measurable after generically adding many Cohen subsets to κ and let be the κ-Rado graph. We prove, for 2 ≤ m < ω, that there is a finite value such that the set [κ] ^m can be partitioned into classes such that for any coloring of any of the classes C _i in fewer than κ colors, there is a copy of in such that is monochromatic. It follows that , that is, for any coloring of with fewer than κ colors there is a copy of such that has at most colors. On the other hand, we show that there are colorings of such that if is any copy of then for all , and hence . We characterize as the cardinality of a certain finite set of types and obtain an upper and a lower bound on its value. In particular, and for m > 2 we have where r _m is the corresponding number of types for the countable Rado graph. Research of M. Džamonja and J. A. Larson were partially supported by Engineering and Physical Sciences Research Council and research of W. J. Mitchell was partly supported by grant number DMS 0400954 from the United States National Science Foundation.     

On end degrees and infinite cycles in locally finite graphs

We introduce a natural extension of the vertex degree to ends. For the cycle space C(G) as proposed by Diestel and Kühn [4, 5], which allows for infinite cycles, we prove that the edge set of a locally finite graph G lies in C(G) if and only if every vertex and every end has even degree. In the same way we generalise to locally finite graphs the characterisation of the cycles in a finite graph as its 2-regular connected subgraphs.     

On embeddability and stresses of graphs

Gluck has proven that triangulated 2-spheres are generically 3-rigid. Equivalently, planar graphs are generically 3-stress free. We show that already the K ₅-minor freeness guarantees the stress freeness. More generally, we prove that every K _r+2-minor free graph is generically r-stress free for 1≤r≤4. (This assertion is false for r≥6.) Some further extensions are discussed. Supported by an I.S.F. grant.     

Kruskal-Katona type theorems for clique complexes arising from chordal and strongly chordal graphs

A forest is the clique complex of a strongly chordal graph and a quasi-forest is the clique complex of a chordal graph. Kruskal-Katona type theorems for forests, quasi-forests, pure forests and pure quasi-forests will be presented.     

On the rigidity of molecular graphs

The rigidity of squares of graphs in three-space has important applications to the study of flexibility in molecules. The Molecular Conjecture, posed in 1984 by T.-S. Tay and W. Whiteley, states that the square G ² of a graph G of minimum degree at least two is rigid if and only if G has six spanning trees which cover each edge of G at most five times. We give a lower bound on the degrees of freedom of G ² in terms of forest covers of G. This provides a self-contained proof that the existence of the above six spanning trees is a necessary condition for the rigidity of G ². In addition, we prove that the truth of the Molecular Conjecture would imply that our lower bound is tight, and would also imply that a conjecture of Jacobs on ‘independent’ squares is valid. This work was supported by an International Joint Project grant from the Royal Society. Supported by the MTA-ELTE Egerváry Research Group on Combinatorial Optimization and the Hungarian Scientific Research Fund grant no. T049671, T60802.     

The intrinsic dimensionality of graphs

We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich [Combinatorica, 1995]. For a graph G, let dim(G) be the smallest d such that G occurs as a (not necessarily induced) subgraph of ℤ_∞ ^d , the infinite graph with vertex set ℤ ^d and an edge (u, v) whenever ∥u − v∥_∞ = 1. The growth rate of G, denoted ρ _G , is the minimum ρ such that every ball of radius r > 1 in G contains at most r ^ρ vertices. By simple volume arguments, dim(G) = Ω(ρ _G ). Levin conjectured that this lower bound is tight, i.e., that dim(G) = O(ρ _G ) for every graph G. Previously, it was unknown whether dim(G) could be bounded above by any function of ρ _G . We show that a weaker form of Levin’s conjecture holds by proving that dim(G) = O(ρ _G log ρ _G ) for any graph G. We disprove, however, the specific bound of the conjecture and show that our upper bound is tight by exhibiting graphs for which dim(G) = Ω(ρ _G log ρ _G ). For several special families of graphs (e.g., planar graphs), we salvage the strong form, showing that dim(G) = O(ρ _G ). Our results extend to a variant of the conjecture for finite-dimensional Euclidean spaces posed by Linial and independently by Benjamini and Schramm. Supported by NSF grant CCR-0121555 and by an NSF Graduate Research Fellowship.     

Drawing 4-Pfaffian graphs on the torus

We say that a graph G is k-Pfaffian if the generating function of its perfect matchings can be expressed as a linear combination of Pfaffians of k matrices corresponding to orientations of G. We prove that 3-Pfaffian graphs are 1-Pfaffian, 5-Pfaffian graphs are 4-Pfaffian and that a graph is 4-Pfaffian if and only if it can be drawn on the torus (possibly with crossings) so that every perfect matching intersects itself an even number of times. We state conjectures and prove partial results for k>5. The author was supported in part by NSF under Grant No. DMS-0200595 and DMS-0701033.     

<Emphasis Type="Italic">K</Emphasis><Subscript>4</Subscript>-free subgraphs of random graphs revisited

In Combinatorica 17(2), 1997, Kohayakawa, ?uczak and Rödl state a conjecture which has several implications for random graphs. If the conjecture is true, then, for example, an application of a version of Szemerédi’s regularity lemma for sparse graphs yields an estimation of the maximal number of edges in an H-free subgraph of a random graph G _{n, p} . In fact, the conjecture may be seen as a probabilistic embedding lemma for partitions guaranteed by a version of Szemerédi’s regularity lemma for sparse graphs. In this paper we verify the conjecture for H = K ₄, thereby providing a conceptually simple proof for the main result in the paper cited above.