DMTCS

2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Stefan Felsner (ed.)

DMTCS Proceedings Volume AE (2005)


If you select a title you will receive more information about the paper and the option to download the paper in PostScript or in Acrobat PDF form:

Contents
Foreword and short abstracts of invited talks
Stefan Felsner
1-4 Colouring random geometric graphs
Colin J. H. McDiarmid and Tobias Müller
5-10 Hypertree-Width and Related Hypergraph Invariants
Isolde Adler, Georg Gottlob and Martin Grohe
11-16 Monotone Boolean Functions with
s
Zeros Farthest from Threshold Functions
Kazuyuki Amano and Jun Tarui
17-20 Pairwise Intersections and Forbidden Configurations
Richard P. Anstee and Peter Keevash
21-24 A sufficient condition for bicolorable hypergraphs
David Défossez
25-30 Decomposable graphs and definitions with no quantifier alternation
Oleg Pikhurko, Joel Spencer and Oleg Verbitsky
31-36 Weak Positional Games on Hypergraphs
Martin Kutz
37-40 Quadratic LYM inequalities
Christian Bey
41-44 Labeling planar graphs with a condition at distance two
Peter Bella, Daniel Král', Bojan Mohar and Katarína Quittnerová
45-50 Fast separation in a graph with an excluded minor
Bruce Reed and David R. Wood
51-56 Supermodularity on chains and complexity of maximum constraint satisfaction
Vladimir Deineko, Peter Jonsson, Mikael Klasson and Andrei Krokhin
57-62 Permutations with short monotone subsequences
Dan Romik
63-66 The game of arboricity
Tomasz Bartnicki, Jarosław Grytczuk and Hal Kierstead
67-72 Directed One-Trees
William Evans and Mohammad Ali Safari
73-76 Deterministic Random Walks on the Integers
Joshua Cooper, Benjamin Doerr, Joel Spencer and Gábor Tardos
77-80 Chromatic Turán problems and a new upper bound for the Turán density of
K
4
-
John Talbot
81-86 On the
L(p,1)
-labelling of graphs
Daniel Gonçalves
87-92 Representations of Edge Intersection Graphs of Paths in a Tree
Martin Charles Golumbic, Marina Lipshteyn and Michal Stern
93-98 Hadamard matrices of order 36
Iliya Bouyukliev, Veerle Fack and Joost Winne
 
99-104 Linear choosability of graphs
Louis Esperet, Mickaël Montassier and André Raspaud
105-110 Removing Even Crossings
Michael J. Pelsmajer, Marcus Schaefer and Daniel Štefankovič
111-116 On the
3/4
-Conjecture for Fix-Free Codes
Christian Deppe and Holger Schnettler
117-122 Color critical hypergraphs and forbidden configurations
Richard Anstee, Balin Fleming, Zoltán Füredi and Attila Sali
123-128 Minor-monotone crossing number
Drago Bokal, Gašper Fijavž and Bojan Mohar
129-132 On the enumeration of uniquely reducible double designs
Veerle Fack, Svetlana Topalova and Joost Winne
133-134 Nonrepetitive colorings of graphs
Noga Alon and Jarosław Grytczuk
135-138 A characterization of extremal graphs with no matching-cut
Paul Bonsma
139-144 Packing non-returning
A
-paths algorithmically
Gyula Pap
145-150 Structure of spaces of rhombus tilings in the lexicograhic case
Éric Rémila
151-156 An upper bound for the chromatic number of line graphs
Andrew D. King, Bruce A. Reed and Adrian R. Vetta
157-160 Connected
τ
-critical hypergraphs of minimal size
Matěj Stehlík
161-166 The Windy Postman Problem on Series-Parallel Graphs
Francisco Javier Zaragoza Mart
í
nez
167-170 Crooked Maps in Finite Fields
Gohar Kyureghyan
171-174 Distance graphs with maximum chromatic number
Javier Barajas and Oriol Serra
175-180 Matroid matching with Dilworth truncation
Márton Makai
181-186 Pebble Game Algorithms and
(k,l)
-Sparse Graphs
Audrey Lee and Ileana Streinu
 
187-192 On the Grone-Merris conjecture
Tamon Stephen
193-198 Improper colouring of (random) unit disk graphs
Ross J. Kang, Tobias Müller and Jean-Sébastien Sereni
199-202
K
-
-factors in graphs
Daniela Kühn and Deryk Osthus
203-206 Finding a Strong Stable Set or a Meyniel Obstruction in any Graph
Kathie Cameron and Jack Edmonds
207-212 NBC Complexes of Convex Geometries
Kenji Kashiwabara and Masataka Nakamura
213-218 Packing Three-Vertex Paths in a Subcubic Graph
Adrian Kosowski and Michał Małafiejski and Paweł Żyliński
219-222 Largest cliques in connected supermagic graphs
Anna Lladó
223-228 Infinite limits and folding
Anthony Bonato and Jeannette Janssen
229-230 Excluded subposets in the Boolean lattice
Gyula O.H. Katona
231-234 Multigraph decomposition into multigraphs with two underlying edges
Miri Priesler and Michael Tarsi
235-238 Mader Tools
Frank Göring
 
239-244 Degree-correlation of Scale-free graphs
Zoran Nikoloski
 
and Narsingh Deo and Ludek Kucera
245-250 Density of universal classes of series-parallel graphs
Jaroslav Nešetřil and Yared Nigussie
 
251-256 Packing triangles in low degree graphs and indifference graphs
Gordana Manić and Yoshiko Wakabayashi
257-262 Semikernels modulo F in Digraphs
Hortensia Galeana-Sánchez and Mucuy-Kak Guevara
263-266 Random Inscribing Polytopes
Ross M. Richardson, Van H. Vu and Lei Wu
267-272 On infinite permutations
Dmitri G. Fon-Der-Flaass and Anna E. Frid
 
273-278 Matchings and Hamilton cycles in hypergraphs
Daniela Kühn and Deryk Osthus
279-284 A Min-Max theorem about the Road Coloring Conjecture
Rajneesh Hegde and Kamal Jain
285-288 Improving the Gilbert-Varshamov bound for
q
-ary codes
Van H. Vu and Lei Wu
289-292 Equivalent Subgraphs of Order 3
Tomoki Nakamigawa
293-298 An extremal problem on trees and database theory
Gyula O.H. Katona and Krisztián Tichler
299-302 On minimal blocking sets of the generalized quadrangle
Miroslava Cimráková and Veerle Fack
303-308 Cycles intersecting edge-cuts of prescribed sizes
Tomáš Kaiser and Riste Škrekovski
309-316 A Probabilistic Counting Lemma for Complete Graphs
Stefanie Gerke, Martin Marciniszyn and Angelika Steger
317-322 Frobenius' Problem
Francesc Aguiló and Alícia Miralles
323-328 Discrepancy of Products of Hypergraphs
Benjamin Doerr, Michael Gnewuch and Nils Hebbinghaus
329-334 Balanced Avoidance Games on Random Graphs
Martin Marciniszyn, Dieter Mitsche and Miloš Stojaković
335-340 Sets of integers without
k+1
coprimes and with specified divisors
Vladimir Blinovsky
341-344 Relaxed Two-Coloring of Cubic Graphs
Robert Berke and Tibor Szabó
 
345-350 Hamiltonian Chains in Hypergraphs
Gyula Y. Katona
351-356 On the Minimum Number of Completely 3-Scrambling Permutations
Jun Tarui
357-362 Negative results on acyclic improper colorings
Pascal Ochem
363-368 Spanning paths in hypercubes
Tomáš Dvořák,
Petr Gregor
and Václav Koubek
369-374 Counting Polyominoes on Twisted Cylinders
Gill Barequet, Micha Moffie, Ares Ribó and Günter Rote
375-378 Local chromatic number and topology
Gábor Simonyi and Gábor Tardos
379-382 Every 3-connected, essentially 11-connected line graph is hamiltonian
Hong-Jian Lai, Yehong Shao, Ju Zhou and Hehui Wu
383-388 On the number of series parallel and outerplanar graphs
Manuel Bodirsky, Omer Giménez, Mihyun Kang and Marc Noy
389-396 Acyclic Coloring of Graphs of Maximum Degree
Δ
Guillaume Fertin and André Raspaud
397-400 Hamiltonian cycles in torical lattices
Vladimir K. Leontiev
 
401-406 Walks reaching a line
Philippe Nadeau
Author Index