Combinatorica

article

Fully-Dynamic Min-Cut*

Mikkel Thorup

Combinatorica > 2007 > 27 > 1 > 91-127

We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in $$ \ifmmode\expandafter\tilde\else\expandafter\~\fi{O}{\left( {{\sqrt n }} \right)} $$ worst-case time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity. Previously, no o(n) bound was known for edge connectivity above 3, and even for...

article

On Stabilizers Of Some Moieties Of The Random Tournament

Eric Jaligot

Combinatorica > 2007 > 27 > 1 > 129-133

Any countably infinite tournament T ₀ embeds as a moiety of the random tournament T in such a way that its setwise stabilizer in Aut(T) is isomorphic to Aut(T ₀).

article

Codes And Xor Graph Products

Noga Alon*, Eyal Lubetzky†

Combinatorica > 2007 > 27 > 1 > 13-33

What is the maximum possible number, f ₃(n), of vectors of length n over {0,1,2} such that the Hamming distance between every two is even? What is the maximum possible number, g ³(n), of vectors in {0,1,2}ⁿ such that the Hamming distance between every two is odd? We investigate these questions, and more general ones, by studying Xor powers of graphs, focusing on their independence number and clique...

article

Vertex-Colouring Edge-Weightings

Louigi Addario-Berry, Ketan Dalal, Colin McDiarmid, Bruce A. Reed, more

Combinatorica > 2007 > 27 > 1 > 1-12

A weighting w of the edges of a graph G induces a colouring of the vertices of G where the colour of vertex v, denoted c _v, is $$ {\sum\nolimits_{e \mathrel\backepsilon v} {w{\left( e \right)}} } $$ . We show that the edges of every graph that does not contain a component isomorphic to K ₂ can be weighted from the set {1, . . . ,30} such that in the resulting vertex-colouring of G, for every edge...

article

An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem*

Lap Chi Lau†

Combinatorica > 2007 > 27 > 1 > 71-90

Given an undirected multigraph G and a subset of vertices S ⊆ V (G), the STEINER TREE PACKING problem is to find a largest collection of edge-disjoint trees that each connects S. This problem and its generalizations have attracted considerable attention from researchers in different areas because of their wide applicability. This problem was shown to be APX-hard (no polynomial time approximation scheme...

article

Three-Color Ramsey Numbers For Paths

András Gyárfás, Miklós Ruszinkó*, Gábor N. Sárközy†, Endre Szemerédi

Combinatorica > 2007 > 27 > 1 > 35-69

We prove—for sufficiently large n—the following conjecture of Faudree and Schelp: $$ R{\left( {P_{n} ,P_{n} ,P_{n} } \right)} = \left\{ {\begin{array}{*{20}c} {{2n - 1{\kern 1pt} \;{\text{for}}\;{\text{odd}}\;n,}} \\ {{{\text{2n - 2}}\;{\text{for}}\;{\text{even}}\;n,}} \\ \end{array} } \right. $$ , for the three-color Ramsey numbers of paths on n vertices.

article

Total Colorings Of Degenerate Graphs

Shuji Isobe, Xiao Zhou, Takao Nishizeki

Combinatorica > 2007 > 27 > 2 > 167-182

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤s. We prove that an s-degenerate graph G has a total coloring with Δ+1 colors if the maximum degree Δ...

article

On The Span Of A Random Channel Assignment Problem

Colin McDiarmid

Combinatorica > 2007 > 27 > 2 > 183-203

In the radio channel assignment problems considered here, we must assign a ‘channel’ from the set 1,2,... of positive integers to each of n transmitters, and we wish to minimise the span of channels used, subject to the assignment leading to an acceptable level of interference. A standard form of this problem is the ‘constraint matrix’ model. The simplest case of this model (the 0, 1 case) is essentially...

article

On Circular Flows Of Graphs

Hong-Jian Lai, Rui Xu, Cun-Quan Zhang*

Combinatorica > 2007 > 27 > 2 > 245-246

A sufficient condition for graphs with circular flow index less than 4 is found in this paper. In particular, we give a simple proof of a result obtained by Galluccio and Goddyn (Combinatorica, 2002), and obtain a larger family of such graphs.

article

The Erdős–Pósa Property For Long Circuits

Etienne Birmelé, J. Adrian Bondy, Bruce A. Reed

Combinatorica > 2007 > 27 > 2 > 135-145

We show that, for every l, the family $$ \mathcal{F}_{l} $$ of circuits of length at least l satisfies the Erdős–Pósa property, with f(k)=13l(k−1)(k−2)+(2l+3)(k−1), thereby sharpening a result of C. Thomassen. We obtain as a corollary that graphs without k disjoint circuits of length l or more have tree-width O(lk ²).

article

An Approximation Scheme For Cake Division With A Linear Number Of Cuts

Jiří Sgall*, Gerhard J. Woeginger

Combinatorica > 2007 > 27 > 2 > 205-211

In the cake cutting problem, n≥2 players want to cut a cake into n pieces so that every player gets a ‘fair’ share of the cake by his own measure. We prove the following result: For every ε>0, there exists a cake division scheme for n players that uses at most c _ε n cuts, and in which each player can enforce to get a share of at least (1-ε)/n of the cake according to his own private measure.

article

A Non-Existence Result For Finite Projective Planes In Lenz-Barlotti Class I.4

Dina Ghinelli, Dieter Jungnickel

Combinatorica > 2007 > 27 > 2 > 163-166

Let Π be a projective plane of order n in Lenz–Barlotti class I.4, and assume that n is a multiple of 3. Then either n=3 or n is a multiple of 9.

article

On The Chromatic Number Of Pentagon-Free Graphs Of Large Minimum Degree

Carsten Thomassen

Combinatorica > 2007 > 27 > 2 > 241-243

We prove that, for each fixed real number c > 0, the pentagon-free graphs of minimum degree at least cn (where n is the number of vertices) have bounded chromatic number. This problem was raised by Erdős and Simonovits in 1973. A similar result holds for any other fixed odd cycle, except the triangle for which there is no such result for c<1/3.

article

Packing Non-Returning A-Paths*

Gyula Pap†

Combinatorica > 2007 > 27 > 2 > 247-251

Chudnovsky et al. gave a min-max formula for the maximum number of node-disjoint nonzero A-paths in group-labeled graphs [1], which is a generalization of Mader's theorem on node-disjoint A-paths [3]. Here we present a further generalization with a shorter proof. The main feature of Theorem 2.1 is that parity is “hidden” inside $$ \ifmmode\expandafter\hat\else\expandafter\^\fi{v} $$ , which is given...

article

Lossless Condensers, Unbalanced Expanders, And Extractors

Amnon Ta-Shma*, Christopher Umans†, David Zuckerman‡

Combinatorica > 2007 > 27 > 2 > 213-240

Trevisan showed that many pseudorandom generator constructions give rise to constructions of explicit extractors. We show how to use such constructions to obtain explicit lossless condensers. A lossless condenser is a probabilistic map using only O(logn) additional random bits that maps n bits strings to poly(logK) bit strings, such that any source with support size K is mapped almost injectively...

article

How To Split Antichains In Infinite Posets*

Péter L. Erdős, Lajos Soukup

Combinatorica > 2007 > 27 > 2 > 147-161

A maximal antichain A of poset P splits if and only if there is a set B ⊂ A such that for each p ∈ P either b ≤ p for some b ∈ B or p ≤ c for some c ∈ A\B. The poset P is cut-free if and only if there are no x < y < z in P such that [x,z]_P = [x,y]_P ∪ [y,z]_P . By [1] every maximal antichain in a finite cut-free poset splits. Although this statement for infinite posets fails (see [2])) we...

article

K ₄-free subgraphs of random graphs revisited

S. Gerke, H. J. Prömel, T. Schickinger, A. Steger, more

Combinatorica > 2007 > 27 > 3 > 329-365

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...

article

Matchings of cycles and paths in directed graphs

Gyula Pap, László Szegő

Combinatorica > 2007 > 27 > 3 > 383-398

In this paper we present a Berge-Tutte-type theorem for a matching problem in directed graphs. This extends the maximum matching problem in undirected graphs, the maximum even factor problem in weakly symmetric directed graphs proposed by W. H. Cunningham and J. F. Geelen in [6], and a packing problem for cycles and edges in undirected graphs. We show an Edmonds-Gallai-type structural description...

article

Lower bound on the profile of degree pairs in cross-intersecting set systems

Zsuzsanna Szaniszló, Zsolt Tuza

Combinatorica > 2007 > 27 > 3 > 399-405

We raise the following problem. For natural numbers m, n ≥ 2, determine pairs d′, d″ (both depending on m and n only) with the property that in every pair of set systems A, B with |A| ≤ m, |B| ≤ n, and A ∩ B ≠ 0 for all A ∈ A, B ∈ B, there exists an element contained in at least d′ |A| members of A and d″ |B| members of B. Generalizing a previous result of Kyureghyan, we prove that all the extremal...

article

On end degrees and infinite cycles in locally finite graphs

Henning Bruhn, Maya Stein

Combinatorica > 2007 > 27 > 3 > 269-291

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...

INFONA - science communication portal

Combinatorica

Fully-Dynamic Min-Cut*

On Stabilizers Of Some Moieties Of The Random Tournament

Codes And Xor Graph Products

Vertex-Colouring Edge-Weightings

An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem*

Three-Color Ramsey Numbers For Paths

Total Colorings Of Degenerate Graphs

On The Span Of A Random Channel Assignment Problem

On Circular Flows Of Graphs

The Erdős–Pósa Property For Long Circuits

An Approximation Scheme For Cake Division With A Linear Number Of Cuts

A Non-Existence Result For Finite Projective Planes In Lenz-Barlotti Class I.4

On The Chromatic Number Of Pentagon-Free Graphs Of Large Minimum Degree

Packing Non-Returning A-Paths*

Lossless Condensers, Unbalanced Expanders, And Extractors

How To Split Antichains In Infinite Posets*

K ₄-free subgraphs of random graphs revisited

Matchings of cycles and paths in directed graphs

Lower bound on the profile of degree pairs in cross-intersecting set systems

On end degrees and infinite cycles in locally finite graphs

Filter options

Publication date

Number

Keywords

INFONA - science communication portal

Combinatorica

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Number

Keywords

Reporting an error / abuse

Sending the report failed

Accessibility options