Bordeaux Graph Workshop
Bordeaux, November 21-24, 2012.
LaBRI, Université Bordeaux 1, 351 cours de la libération, Talence, France.
> [BGW 2012] / List of accepted papers

BGW 2012 is the second edition of Bordeaux Graph Workshop.
Organized by the "Graphs and Applications" group.

List of accepted papers

  • Pierre Aboulker. Excluding 4-wheels.
  • Pierre Aboulker and Nicolas Bousquet. Graphs with no cycle with a fixed number of chords.
  • Pierre Aboulker, Zhentao Li and Stéphan Thomassé. Clock-free graphs and k-clock-free graphs of high girth.
  • Pierre Aboulker, Marko Radovanovic, Nicolas Trotignon, Théophile Trunck and Kristina Vuskovic. Linear balanceable and subcubic balanceable graphs.
  • Boris Albar and Daniel Gonçalves. Stress freeness of K_d minor free graphs.
  • Stephan Dominique Andres and Winfried Hochstättler. Generalizing the Strong Perfect Graph Theorem to digraphs.
  • Julio Araujo, Grégory Morel, Leonardo Sampaio, Ronan Soares and Valentin Weber. Hull number: {P5,K3}-free graphs and reduction rules.
  • Christine Bachoc, Arnaud Pecher and Alain Thiéry. On the theta number of circular-cliques and some consequences.
  • Robert F. Bailey, José Cáceres, Delia Garijo, Antonio González, Alberto Marquez, Karen Meagher and María Luz Puertas. Resolving sets for Johnson and Kneser graphs.
  • Joergen Bang-Jensen and Alessandro Maddaloni. Arc-disjoint paths in decomposable digraphs.
  • Rommel Barbosa, Dieter Rautenbach and Márcia Santana. On Graphs with Maximal Independent Sets of Few Sizes, Minimum Degree at least 2, and Girth at least 7.
  • Laurent Beaudou. On some facility location problem.
  • Siham Bekkai. Generalizing [2,b]-factors.
  • Pascal Berthomé, Tom Bouvier, Frédéric Mazoit, Nicolas Nisse and Ronan P Soares. A Unified FPT Algorithm for Width of Partition Functions.
  • Marthe Bonamy, Nicolas Bousquet and Hervé Hocquard. Adjacent vertex-distinguishing edge coloring of graphs with bounded maximum degree.
  • Marthe Bonamy, Benjamin Leveque and Alexandre Pinlou. Graphs with mad<3 and Delta>=17 are list 2-distance (Delta+2)-colorable.
  • Csilla Bujtás, S. Aparna Lakshmanan and Zsolt Tuza. Generalized line graphs: Cartesian products and complexity of recognition.
  • Jose Caceres, Maria Morales, Auxiliadora Moreno and Maria Luz Puertas. Supergeodetic sets in graphs.
  • Roman Čada, Jan Ekstein, Přemysl Holub and Olivier Togni. Radio Labelings of Distance Graphs.
  • Rocío Moreno Casablanca, Pedro García Vázquez, Ana Dianez and Encarnación Abajo Casado. On average fault-tolerance in product graphs.
  • Clément Charpentier. Minmax Degree of planar graphs without 4-cycles and i-cycles.
  • G.L. Chia, W. Hemakul and S. Singhun. Graphs with Cyclomatic Number Three having Panconnected Square.
  • Maria Chudnovsky and Paul Seymour. Excluding paths and antipaths.
  • Derek G. Corneil, Jérémie Dussart and Michel Habib. Fixed point properties for Lexicographic Breadth First Search on cocomparability graphs.
  • Bruno Courcelle. The atomic decomposition of strongly connected graphs.
  • Christophe Crespelle and Philippe Gambette. (Nearly-)Tight Bounds on the Linearity and Contiguity of Cographs.
  • César Hernández Cruz and Pavol Hell. On the complexity of the 3-kernel problem in some classes of digraphs.
  • Maria Del Rocio Sanchez Lopez and Hortensia Galeana Sanchez. H-kernels in infinite digraphs.
  • Ewa Drgas-Burchardt. On stable matchings in the Gale-Shapley model.
  • Louis Esperet and Aline Parreau. Acyclic edge-coloring of graphs using entropy compression.
  • Sergei Evdokimov. On automorphism groups of circulant graphs.
  • Jiří Fiala, Jan Hubička and Yangjing Long. Constrained Homomorphism Orders.
  • Florent Foucaud and Reza Naserasr. Bounding K4-minor-free graphs in the homomorphism order.
  • Nicolas Gastineau and Sebastien Tavenas. Complexity of Generalized Distance Coloring Problem.
  • Cyril Gavoille and Pierre Halftermeyer. Connectivity Labeling Scheme for Graphs on Surface.
  • Sylvain Gravier and Elise Vandomme. Constant 2-labelling of weighted cycles.
  • Ararat Harutyunyan and Bojan Mohar. Colorings and acyclic sets in planar graphs and digraphs.
  • Hervé Hocquard, Mickael Montassier, André Raspaud and Petru Valicov. A note on strong edge-colouring.
  • Arthur Hoffmann-Ostenhof. Structures in Cubic Graphs.
  • Chun-Chung Hsieh. Knot theory and Feynman graphs.
  • Jan Hubicka, Juergen Jost, Yangjing Long, Peter F. Stadler and Ling Yang. Relation between Graphs.
  • Wilfried Imrich. Symmetry breaking in graphs.
  • Stanislav Jendrol. Cyclic words and vertex colourings of plane graphs.
  • Katarzyna Jesse-Józefczyk and Elzbieta Sidorowicz. Claw-free cubic graphs and their global secure sets.
  • Ville Junnila and Tero Laihonen. Identification of sets of edges using factors.
  • Frantisek Kardos. Almost all fullerene graphs are almost Hamiltonian.
  • Arnfried Kemnitz and Massimiliano Marangio. d-Strong Edge and Total Colorings of Graphs.
  • Martin Knor. Efficient domination in vertex-transitive cubic graphs.
  • Mélodie Lapointe, Alexandre Blondin Massé, Philippe Galinier, Mélanie Lord and Odile Marcotte. Enumerating minimum feedback vertex sets in directed graphs.
  • Anh Vinh Le. On (3,t)-existentially closed graphs constructed from permutation polynomials.
  • Nicolas Lichiardopol. Strong connectivity and directed triangles in oriented graphs. Partial results on a particular case of the Caccetta-Häggkvist conjecure.
  • Henry Liu, Rui Carpentier, Manuel Silva and Teresa Sousa. Rainbow Connection in Hypergraphs.
  • Chun-Hung Liu and Gexin Yu. Linear colorings of subcubic graphs.
  • Giuseppe Mazzuoccolo. How many m-matchings are necessary to cover the edge-set of a graph?
  • Houcine Boumediene Merouane and Mustapha Chellali. Dominator chromatic number of a tree.
  • Mirka Miller, Joe Ryan, Zdenek Ryjacek, Jakub Teska and Petr Vrana. Closures and stability of hereditary classes of graphs.
  • Mickael Montassier, Arnaud Pecher, Guillem Perarnau and Oriol Serra. Choosability of Partitions.
  • Jan Obdrzalek, Robert Ganian, Petr Hlineny, Jaroslav Nesetril, Patrice Ossona De Mendez and Reshma Ramadurai. Shrub depth, m-partite cographs and MSO1.
  • Paulraja Palanivel Subramania Nadar and Sampath Kumar S. Edge-Disjoint Hamilton Cycles in Knodel Graphs.
  • P. Paulraja and S. Sivasankar. Linear Arboricity of Tensor Products of Graphs.
  • Guillem Perarnau and Giorgis Petridis. Matchings in Random Biregular Bipartite Graphs.
  • Jakub Przybylo. Proper edge colourings distinguishing colour pallets of the neighbours - algorithms enhanced by Combinatorial Nullstellensatz.
  • Robert Samal. Lovász theta function and products of graphs.
  • Joe Sawada. On k-critical P5-free graphs.
  • Ingo Schiermeyer. Hunting for rainbow bulls and diamonds.
  • Sagnik Sen. Largest planar ocliques.
  • Sven Simonsen, Jørgen Bang-Jensen and Alessandro Maddaloni. Finding Quasi-Hamiltonian Paths and Cycles in Semicomplete Multipartite Digraphs.
  • Teresa Sousa. Minimum Weight H-Decompositions of Graphs: The Bipartite Case.
  • Eckhard Steffen. Balanced valuations and circular flows.
  • J.A. Telle and Y. Villanger. FPT algorithms for domination in biclique-free graphs.
  • Ingrid Torres. γ-H-cycles in H-edge coloured digraphs.
  • Margit Voigt, Anja Pruchnewski and Arnfried Kemnitz. (r,s)-Fractional (P,Q)-Total Colorings of Graphs.
  • Mariusz Wozniak. Minimum number of palettes in edge colorings.

CNRS Chaire
Communauté Urbaine de Bordeaux
Conseil Régional
Maths ŕ Modeler
Office du tourisme de Bordeaux
Région Aquitaine
Université Bordeaux 1