7th International Colloquium on Graph Theory
ICGT '05

Invited Speakers
List of participants
Abstract Submission

Provisional programme

September 11
September 12
September 13
September 14
September 15
September 16
08:00 – 08:50   Registration        
08:50 – 09:00 Opening
09:00 – 10:00 Invited talk 1
N. Alon
Invited talk 3
M .Chudnovsky
Invited talk 5
P. Seymour
Invited talk 6
X. Zhu
Invited talk 8
J. van den Heuvel
10:00 – 10:20 Coffee break Coffee break Coffee break Coffee break Coffee break
10:20 – 10:45 A1B1C1 D1E1F1 G1H1I1 J1K1L1 M1N1O1
10:45 – 11:10 A2B2C2 D2E2F2 G2H2I2 J2K2L2 M2N2O2
11:10 – 11:35 A3B3C3 D3E3F3 G3H3I3 J3K3L3 M3N3O3
11:35 – 11:50 Coffee break Coffee break Coffee break Coffee break Coffee break
11:50 – 12:15 A4B4C4 D4E4F4 G4H4I4 J4K4L4 M4N4O4
12:15 – 12:40 A5B5C5 D5E5F5 G5H5I5 J5K5L5 M5N5O5
14:00 – 14:25   D6E6F6 Excursion   Invited talk 8
C. Thomassen
14:25 – 14:50 D7E7F7
14:50 – 15:15 D8E8F8
15:15 – 15:35 Invited talk 2
J. Nesetril
Coffee break Invited talk 6
R. Thomas
Coffee break
15:35 – 16:15 Invited talk 4
O. Borodin
16:15 – 16:35 Coffee break Coffee break
16:35 – 17:00 A6B6C6 Problem session J6K6L6
17:00 – 17:25 A7B7C7 J7K7L7
17:25 – 17:50 A8B8C8 Football game J8K8L8
19:00 – 20:00 Welcome
19:00 – 22:00 Registration        

Plenary lectures

Noga ALON, Testing Properties of Large Graphs
Oleg V. BORODIN, t. b. a.
Maria CHUDNOVSKY, The structure of bullfree graphs
Jan van den HEUVEL, Mixing Colours in Graphs
Jaroslav NESETRIL, Bounded expansions versus minors
Paul D. SEYMOUR, Colouring and list-colouring claw-free graphs
Robin THOMAS, Large 6-connected graphs with no K_6 minor
Carsten THOMASSEN, Graphs and sets in the plane
Xuding ZHU, Distinguishing labeling of graphs and group actions

Contributed talks

Chair: P. Seymour Chair: C. Thomassen Chair: A. Raspaud
A1 About counterexamples to the 5-flow conjectures, M. Kochol B1 Connected graph searching in outerplanar graphs, F. Fomin, D. Thilikos and I. Todinca C1 Algorithms for 3PC(.,.)-free Berge graphs, F. Maffray, N. Trotignon and K. Vuskovic
A2 Unions of perfect matchings in cubic graphs, T. Kaiser, D. Kral and S. Norine B2 Symmetry and connectivity in G-graphs, A. Bretto and L. Gillibert C2 Characterization and recognition of Helly circular-arc clique-perfect graphs, F. Bonomo and G. Duran
A3 Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs, C. Bentz B3 Crossing minimisation heuristic for 2-page drawings, H. He, O. Sykora and I. Vrt'o C3 Colouring some kinds of perfect graphs robustly, K. Cameron and J. Edmonds
A4 Fractional covering by cuts, R. Samal B4 Mixed covering of trees and the augmentation problem with odd diameter constraints, V. Chepoi, B. Estellon, K. Nouioua and Y. Vaxès C4 On strongly circular-perfectness, S. Coulonges, A. Pecher and A. K. Wagler
A5 A proof of a conjecture of Sabidussi on graphs idempotent under the lexicographic product, P. Ille B5 Extremities and orderings defined by generalized graph search algorithms, A. Berry, J. Blair, J.-P. Bordat, R. Krueger and G. Simonet C5 Coloring Meyniel graphs in linear time, B. Lévêque and F. Maffray
Chair: J. Nesetril Chair: C. Paul Chair: P. Hansen
A6 The cyclic antibandwidth problem, O. Sykora, L. Torok and I. Vrt'o B6 Distance labeling for permutation graphs, F. Bazzaro and C. Gavoille C6 Edge intersection graphs of linear 3-uniform hypergraphs, P. V. Skums, S. V. Suzdal and R.I. Tyshkevich
A7 Edge-maximal graphs of branchwidth k, C. Paul and J.A. Telle B7 Edge addition number of cartesian product of paths and cycles, Yung-Ling Lai, Chang-Sin Tian, Ting-Chun Ko C7 Every monotone 3-graph property is testable, C. Avart, V. Rodl and M. Schacht.
A8 The grad of a graph and classes with bounded expansion,J. Nesetril and P. Ossona de Mendez B8 Hamiltonian cycles and paths through, D. Amar, E. Flandrin and G. Gancarzewicz C8 Cover pebbling thresholds for the complete graph, A. Godbole, N. Watson and C. Yerger
Chair: R. Thomas Chair: J. van den Heuvel Chair: F. Havet
D1 Graph decompositions definable in monadic second-order logic, B. Courcelle E1 Priority-consistent graphs, A. Farley and A. Proskurowski F1 New sufficient conditions for the existence of kernels in digraphs, H. Galeana-Sánchez, M. Guevara
D2 The bi-join decomposition, F. de Montgolfier and M. Rao E2 Degree conditions and degree bounded trees, H. Matsumura F2 Transitive convex subsets in large tournaments, Bertrand Jouve
D3 A representation for the modular-pairs of a P4-reducible graph by modular decomposition, S. Klein, N. C. dos Santos and J. L. Szwarcfiter E3 Some results on the wiener index of iterated line graphs, A. A. Dobrynin and L. S. Mel'nikov F3 Functional graphs, A. El Sahili
D4 Rank-width and well-quasi-ordering of skew-symmetric matrices, S. Oum E4 Around Wythoff's game, E. Duchêne, S. Gravier and M. Mhalla F4 Quasi-amply-regularity and generalized Hamming graphs, F. Affif Chaouche and A.Berrachedi
D5 Graph decompositions for cartesian products, S. Djelloul E5 On the metric dimension of some families of graphs, J. Caceres, C. Hernando, M. Mora, Ignacio M. Pelayo, M. L. Puertas and C. Seara F5 2-1 routing requests in the hypercube, O. Baudon
Chair: M. Kochol Chair: F. Maffray Chair: M. Golumbic
D6 Some families of arbitrarily vertex decomposable graphs, R. Kalinowski, M. Pilsmiak, M. Wozniak and I. Ziolo E6 Parameters of connectivity in (a,b)-linear graphs, C. Silva Oliveira; N. M. Maia de Abreu and A. Fernando Pazoto F6 Embedding some hierarchical caterpillars into hypercube, V. Sunitha
D7 An Ore-type condition for arbitrarily vertex decomposable graphs, A. Marczyk E7 The P_4-sparse graph sandwich problem, A. Morgana, S. Dantas, S. Klein and C. P. de Mello F7 On the structure of identifiable graphs, I. Charon, O. Hudry and A. Lobstein
D8 Packings and 2-packings of A-paths, G. Pap E8 Helly property and sandwich graphs, R B. Teixeira, M. C. Dourado, P. Petito F8 Comparing recent methods in graph partitioning, A. Guénoche
Chair: E. Flandrin Chair: B. Courcelle Chair: N. Alon
G1 Recent results on disjoint cycles in graphs, S. Fujita H1 Oriented forests in directed graphs, Ch. Sobhan Babu and A. A. Diwan I1 Perfect codes in direct products of cycles, S. Spacapan
G2 Heavy cycles in weighted graphs, J. Fujisawa H2 On some arboricities in planar graphs, D. Goncalves and P. Ochem. I2 Perfect codes in Cartesian products of hypercube and multidimansionnal grid, P. Dorbec and M. Mollard
G3 Unicycle graphs and uniquely restricted maximum matchings, V. E. Levit and E. Mandrescu H3 Edge Partition of Toroidal Graphs into Forests in Linear Time, N. Bonichon, C. Gavoille and A. Labourel I3 Codes identifying vertices in graphs, J. Moncel
G4 Non-zero disjoint cycles in highly connected group labeled graphs, Ken-ichi Kawarabayashi, Paul Wollan H4 The positive lightness of digraphs, embeddable in a surface, without 4-cycles S. D. Andres I4 The reduced Prufer code for rooted labelled k-trees, P.R. Costa Pereira, L. Markenzon and O. Vernet
G5 Minimum cycle bases of graphs over different fields, J. D. Horton and F. Berger H5 The pure prime circle orbit conjecture, F. Genest I5 Read-once functions revisited and the readability number of a boolean function, M. C. Golumbic, A. Mintz and U. Rotics
Chair: X. Zhu Chair: M. Chudnovsky Chair: A. Bondy
J1 Set colorings of graphs, S.M. Hegde K1 Claw-free graphs with non-clique $mu$-subgraphs and related geometries, I.A. Vakula L1 Circulant graphs: efficient recognizing and isomorphism testing, S. Evdokimov and I. Ponomarenko
J2 Ordered 3-colorings, A. Gupta, J. Manuch, L. Stacho and X. Zhao K2 On an extension of distance hereditary graphs, M. Aider and K. Meslem L2 Characterizing Cographs (k,l)-partitionable, R. de Souza Francisco, S. Klein and L. Tito Nogueira
J3 Sum coloring of distance and circulant graphs, B. Effantin and H. Kheddouci K3 The maximal restricted edge connectivity of Kautz undirected graphs, S. Wang and S. Lin L3 Simple vertex ordering characterizations for graph search, D. G. Corneil and R. Krueger
J4 Bicolored matchings in some classes of graphs, M-C. Costa, D. de Werra, C. Picouleau and B. Ries K4 P-antiregular graphs, P. O. Boaventura-Netto L4 Perfect matchings of the small polyominoes, B. Dong and F. Zhang
J5 Coloring the Cartesian sum of graphs, D. Liu and X. Zhu K5 Homogeneously almost self-complementary graphs, P. Potocnik and M. Sajna L5 On upper bound graphs with forbidden subposets, H. Era, K. Ogawa, S. Tagusari and M. Tsuchiya
Chair: K. Cameron Chair: P. Hell Chair: R. Woodrow
J6 2-local distributed algorithms for generalized coloring of hexagonal graphs, P. Sparl and Janez Zerovnik K6 On the structure of self-complementary graphs, N. Trotignon L6 On posets of pagenumber 2, A. B. Kwiatkowska and M. Syslo
J7 Nonrepetitive colorings of graphs, Noga Alon, Jaroslaw Grytczuk K7 Paired-domination of Cartesian products of graphs and rainbow domination, B. Bresar L7 On the domatic and the total domatic numbers of the 2-section graph of the order interval hypergraph of a finite poset, I. Bouchemakh and S. Ouatiki
J8 Improper colouring of unit disk graphs, F. Havet, R. J. Kang and J.-S. Sereni K8 On maximum number of minimal dominating sets in graphs, F. V. Fomin, F. Grandoni, A. V. Pyatkin and A. A. Stepanov L8 Faithful extensions on finite orders classes, A. Guillet, J. Leblet, J.-X. Rampon
Chair: J.-C. Bermond Chair: Chair: S. Thomassé
M1 Analysis of optimal sets of survivable paths in undirected simple graph applicable for optical networks, Z. R. Bogdanowicz N1 Abelian colourings of cubic graphs, E. Macajova, A. Raspaud and M. Skoviera O1 2K_2-Partition Problem, C. N. Campos, S. Dantas, L. Faria and S. Gravier
M2 A random graph model of mobile wireless networks, T. Tyrakowski and Z. Palka N2 Existence and colouring of configurations with line size k=4, Harald Gropp O2 Optimal partition of a bipartite graph with prescribed layout into non-crossing b-matchings, F. Malucelli and S. Nicoloso
M3 Radio k-labelings for cartesian products of graphs M. Kchikech, R. Khennoufa and O. Togni N3 The total chromatic number of some bipartite graphs, C. N. Campos and C. P. de Mello O3 Edge disjoint paths of increasing order in complete bipartite graphs, P. Hamburger and W. Cao
M4 AutoGraphiX: a survey, M. Aouchiche, G. Caporossi, P. Hansen and M. Laffay N4 Circumferences and minimum degrees in 3-connected Claw-Free graphs, M. Li O4 Some algorithms on conditionally critical indecomposable graphs, C. K. Dubey, S. K. Mehta
M5 Loop graphs and asteroidal sets, L. Alcón, M.R. Cerioli, C.M.H. de Figueiredo, M. Gutiérrez and J. Meidanis N5 Forbidden minors and subdivisions for toroidal graphs with no $K_{3,3}, A. Gagarin, W. Myrvold and J. Chambers O5 On a weighted generalization of $alpha$-critical graphs, J.-P. Doignon, S. Fiorini and G. Joret

Overhead projectors and data/video projectors will be available in the session rooms. Computer presentation speakers should bring and use their own laptop/notebook, which will be connected to the data/video projector provided.

Home |  Objectives |  Committees |  Invited Speakers |  List of participants |  Submission |  Programme |  Registration |  Travel