Search

Your search keyword '"Department of Applied Mathematics (KAM) (KAM)"' showing total 36 results
Start Over Author "Department of Applied Mathematics (KAM) (KAM)" Publisher hal ccsd
36 results on '"Department of Applied Mathematics (KAM) (KAM)"'

1. On Fractional Fragility Rates of Graph Classes

Author

Dvořák, Zdeněk, Sereni, Jean-Sébastien, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Centre National de la Recherche Scientifique (CNRS), Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Réseau nanophotonique et optique, Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Matériaux et nanosciences d'Alsace (FMNGE), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Sereni, Jean-Sébastien, École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, and Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

International audience; We consider, for every positive integer a, probability distributions on subsets of vertices of a graph with the property that every vertex belongs to the random set sampled from this distribution with probability at most 1/a. Among other results, we prove that for every positive integer a and every planar graph G, there exists such a probability distribution with the additional property that for any set X in the support of the distribution, the graph G − X has component-size at most (∆(G) − 1) a+O(√ a) , or treedepth at most O(a 3 log 2 (a)). We also provide nearly-matching lower bounds.

Published
2020

2. Embeddability in R^3 is NP-hard

Author

Eric Sedgwick, Arnaud de Mesmay, Martin Tancer, Yo'av Rieck, GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Centre National de la Recherche Scientifique (CNRS), University of Arkansas [Fayetteville], School of Computing [DePaul] (SOC), DePaul University [Chicago], Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, de Mesmay, Arnaud, Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Department of Applied Mathematics [Prague] (KAM), and Charles University [Prague] (CU)

Subjects
Reduction (recursion theory), Boundary (topology), 0102 computer and information sciences, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Combinatorics, Computational topology, Simplicial complex, Dehn surgery, Artificial Intelligence, [MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT], 0101 mathematics, Unknot, Mathematics::Symplectic Geometry, Time complexity, ComputingMilieux_MISCELLANEOUS, [MATH.MATH-GT] Mathematics [math]/Geometric Topology [math.GT], Mathematics, 010102 general mathematics, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], 010201 computation theory & mathematics, Hardware and Architecture, Control and Systems Engineering, Computational problem, Software, Information Systems
Abstract

We prove that the problem of deciding whether a two- or three-dimensional simplicial complex embeds into R 3 is NP -hard. Our construction also shows that deciding whether a 3-manifold with boundary tori admits an S 3 filling is NP -hard. The former stands in contrast with the lower-dimensional cases, which can be solved in linear time, and the latter with a variety of computational problems in 3-manifold topology, for example, unknot or 3-sphere recognition, which are in NP ∩ co- NP. (Membership of the latter problem in co-NP assumes the Generalized Riemann Hypotheses.) Our reduction encodes a satisfiability instance into the embeddability problem of a 3-manifold with boundary tori, and relies extensively on techniques from low-dimensional topology, most importantly Dehn fillings of manifolds with boundary tori.

Published
2018

3. Colouring Edges with many Colours in Cycles

Author

Xuding Zhu, Jaroslav Nešetřil, P. Ossona de Mendez, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Centre d'Analyse et de Mathématique sociales (CAMS), École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics [Hangzhou], Zhejiang University, and European Project: LEA STRUCO

Subjects
Discrete mathematics, Arboricity, Multigraph, Graph, Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, Bounded function, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Partition (number theory), Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics
Abstract

International audience; The arboricity of a graph G is the minimum number of colours needed to colour the edges of G so that every cycle gets at least two colours. Given a positive integer p, we define the generalized p-arboricity Arb_p(G) of a graph G as the minimum number of colours needed to colour the edges of a multigraph G in such a way that every cycle C gets at least min(|C|; p + 1) colours. In the particular case where G has girth at least p + 1, Arb_p(G) is the minimum size of a partition of the edge set of G such that the union of any p parts induce a forest. If we require further that the edge colouring be proper, i.e., adjacent edges receive distinct colours, then the minimum number of colours needed is the generalized p-acyclic edge chromatic number of G. In this paper, we relate the generalized p-acyclic edge chromatic numbers and the generalized p-arboricities of a graph G to the density of the multigraphs having a shallow subdivision as a subgraph of G.

Published
2014

4. Structural and anisotropy of magnetic susceptibility records of granitoid sheets emplacement during growth of a continental gneiss dome (Central Sudetes, European Variscan Belt)

Author

Lehmann, J., Schulmann, Karel, Edel, J.-B., Jezek, Josef, Hrouda, F., Lexa, O., Chopin, F., Dynamique de la lithosphère et des bassins sédimentaires (IPGS) (IPGS-Dylbas), Institut de physique du globe de Strasbourg (IPGS), Université de Strasbourg (UNISTRA)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National de la Recherche Scientifique (CNRS), Université de Strasbourg (UNISTRA)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National de la Recherche Scientifique (CNRS), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Institute of Petrology and Structural Geology (IPSG), Charles University [Prague] (CU), Czech Geological Survey [Praha], Institute of Petrology and Structural geology, Ecole et Observatoire des Sciences de la Terre (EOST), and ANR-06-BLAN-0352,LFO in orogens,Laterally-forced overturns (LFO) enhanced by melt induced softening (MIS) in orogens: new model for continental tectonics(2006)

Subjects
[SDU.STU.TE]Sciences of the Universe [physics]/Earth Sciences/Tectonics, PLASTIC-DEFORMATION, NORTHEASTERN MARGIN, [SDE.MCG]Environmental Sciences/Global Changes, EASTERN VARISCIDES, FABRIC DEVELOPMENT, BOHEMIAN MASSIF, TONALITE SILL, MELT SEGREGATION, PRE-VARISCAN
Abstract

International audience; Granitoid magmatic sheets emplaced syntectonically during growth of the Orlica-nienik mantled gneiss dome (Central Sudetes, European Variscan belt) were examined by means of structural geology, quartz, and anisotropy of magnetic susceptibility (AMS) fabric studies. Magmatic emplacement was localized along the eastern transpressive margin of the high metamorphic core and below the low-grade detached mantle rimming the southern margin of the dome. In the first area, the magmatic sheets were emplaced parallel to the dilated subhorizontal foliation of an anisotropic pre-orogenic block. The resulting melt-host rock multilayer localized the transpressive zone along which the bulk of magma was emplaced. The AMS study shows an across-strike fabric zonation underlying a strongly transpressive solid-state deformation in the hanging-wall, magmatic subhorizontal fabric in the foot-wall and a transitional fabric in the center of the intrusion. In contrast, along the southern dome margin, magmatic sheets intruded along steep foliations of weakly metamorphic mantle rocks, and are affected by recumbent folding and subhorizontal shearing. The bulk of the sheets present a shallow-dipping magmatic foliation and an along-strike magmatic lineation. The variations of the quartz and magnetic fabrics are attributed to superimposition of pure shear-dominated ductile thinning followed by simple shear-dominated detachment onto the original steep fabric. AMS modeling confirms the role of variation of orientation of pre-intrusive anisotropy during progressive deformation on the resulting fabric pattern and helps explaining observed variations in fabric orientations and symmetries. This study highlights contrasting mechanical behavior of syntectonically emplaced magmas in different parts of a growing crustal-scale mantled gneiss dome. Keywords

Published
2013

5. Modified Jeffery model: Influence of particle concentration on mineral fabric in moderately concentrated suspensions

Author

Jezek, Josef, Schulmann, Karel, Paterson, S., Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Dynamique de la lithosphère et des bassins sédimentaires (IPGS) (IPGS-Dylbas), Institut de physique du globe de Strasbourg (IPGS), Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-Institut national des sciences de l'Univers (INSU - CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-Institut national des sciences de l'Univers (INSU - CNRS), and UCLA

Subjects
[SDU.STU.TE]Sciences of the Universe [physics]/Earth Sciences/Tectonics, [SDE.MCG]Environmental Sciences/Global Changes, parasitic diseases, technology, industry, and agriculture, Physics::Optics
Abstract

International audience; A modified Jeffery model involving particle interactions allows the simulation of preferred orientation of crystals and the anisotropy of magnetic susceptibility in magmatic flow with up to 40% of rigid particle fraction. Numerical simulations are compared to analogue and natural fabrics. A study of the role of particle concentration shows that the increasing percentage of crystal fraction in dilute suspensions leads to progressive attenuation of the fabric intensity and cyclicity. At high strains in simple shear flow, the lineation converges to a constant value close to the shear plane. With increasing particle concentration, the fabric diverges from the shear direction reflecting the effect of increased crystal tiling. The model can be applied to quantify mineral preferred orientations of crystal mushes in magmatic fabric studies.

Published
2013

6. Characterization of graphs and digraphs with small process number

Author

David Coudert, Jean-Sébastien Sereni, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)

Subjects
Discrete mathematics, Vertex (graph theory), Applied Mathematics, Rerouting, Pathwidth, 020206 networking & telecommunications, Digraph, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Combinatorics, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Process number, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Vertex separation, Discrete Mathematics and Combinatorics, Time complexity, Mathematics
Abstract

International audience; We introduce the process number of a digraph as a tool to study rerouting issues in \wdm networks. This parameter is closely related to the vertex separation (or pathwidth). We consider the recognition and the characterization of (di)graphs with small process number. In particular, we give a linear time algorithm to recognize (and process) graphs with process number at most 2, along with a characterization in terms of forbidden minors, and a structural description. As for digraphs with process number 2, we exhibit a characterization that allows one to recognize (and process) them in polynomial time.

Published
2011

7. Exact Algorithms for L(2,1)-Labeling of Graphs

Author

Martin Klazar, Mathieu Liedloff, Jan Kratochvíl, Frédéric Havet, Dieter Kratsch, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'Informatique Théorique et Appliquée (LITA), Université de Lorraine (UL), Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges

Subjects
Vertex (graph theory), Discrete mathematics, 021103 operations research, General Computer Science, Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Graph, Computer Science Applications, Exponential function, Running time, Combinatorics, Dynamic programming, Exact algorithm, 010201 computation theory & mathematics, Common neighbor, Theory of computation, Algorithm, Mathematics
Abstract

International audience; The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph $G=(V,E)$ into an interval of integers $\{0, \dots ,k\}$ is an $L(2,1)$-labeling of $G$ of span $k$ if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed $k\ge 4$, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive $O^*((k+1)^n)$ algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of $k=4$, where the running time of our algorithm is $O(1.3006^n)$. Furthermore we show that dynamic programming can be used to establish an $O(3.8730^n)$ algorithm to compute an optimal $L(2,1)$-labeling.

Published
2011

8. How many F's are there in G?

Author

Nesetril, Jaroslav, Ossona De Mendez, Patrice, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Centre d'Analyse et de Mathématique sociales (CAMS), and École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Abstract

International audience; We prove that the asymptotic logarithmic density of copies of a graph $F$ in the graphs of a nowhere dense class $\mathcal C$ is integral and we determine the range of its possible values. This leads to a generalization of the Trichotomy theorem \cite{ND_characterization} and to a notion of degree of freedom of a graph $F$ in a class $\mathcal C$. This provides yet another formulation of the somewhere dense -- nowhere dense classification. We obtain a structural result about the asymptotic shape of graphs with given degree of freedom.

Published
2011

9. 5-colouring graphs with 4 crossings

Author

Rok Erman, Ondřej Pangrác, Bernard Lidický, Frédéric Havet, Departement of Mathematics [Slovenia], University of Ljubljana, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Institute for Theoretical Computer Science (ITI), Charles University [Prague] (CU), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)

Subjects
Discrete mathematics, Block graph, Clique-sum, General Mathematics, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Clique graph, 01 natural sciences, 1-planar graph, Simplex graph, Treewidth, Combinatorics, 010201 computation theory & mathematics, Split graph, Crossing number (graph theory), 0101 mathematics, Mathematics
Abstract

International audience; We answer in the negative a question of Oporowski and Zhao [Discrete Math., 309 (2009), pp. 2948-2951] asking whether every graph with crossing number at most 5 and clique number at most 5 is 5-colorable. However, we show that every graph with crossing number at most 4 and clique number at most 5 is 5-colorable. We also show some colorability results on graphs that can be made planar by removing a few edges. In particular, we show that, if a graph with clique number at most 5 has three edges whose removal leaves the graph planar, then it is 5-colorable.

Published
2011

10. On the sextet polynomial of fullerenes

Author

Sereni, Jean-Sébastien, Stehlík, Matej, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF), and Sereni, Jean-Sébastien

Subjects
[CHIM.THEO]Chemical Sciences/Theoretical and/or physical chemistry, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [CHIM.THEO] Chemical Sciences/Theoretical and/or physical chemistry, Perfect matchings, Kekulé count, Fullerenes, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Resonant pattern, Sextet polynomial
Abstract

International audience; We show that the sextet pattern count of every fullerene is strictly smaller than the Kekulé structure count. This proves a conjecture of Zhang and He [J Math Chem 38(3):315-324 (2005)].

Published
2010

11. Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree

Author

Stéphane Bessy, Nicolas Lichiardopol, Jean-Sébastien Sereni, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Lycée Adam de Craponne, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), and Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)

Subjects
0102 computer and information sciences, 02 engineering and technology, Cycle, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Mathematical proof, 01 natural sciences, Theoretical Computer Science, Collatz conjecture, Combinatorics, Set (abstract data type), Integer, Computer Science::Discrete Mathematics, Circuit, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, The Bermond–Thomassen conjecture, Mathematics, Discrete mathematics, Conjecture, Digraph, 020206 networking & telecommunications, 010201 computation theory & mathematics, Bounded function, In degree, Tournament
Abstract

International audience; The Bermond-Thomassen conjecture states that, for any positive integer r, a digraph of minimum out-degree at least 2r − 1 contains at least r vertex-disjoint directed cycles. Thomassen proved that it is true when r = 2, and very recently the conjecture was proved for the case where r = 3. It is still open for larger values of r, even when restricted to (regular) tournaments. In this paper, we present two proofs of this conjecture for tournaments with minimum in-degree at least 2r − 1. In particular, this shows that the conjecture is true for almost regular tournament. In the first proof, we prove auxiliary results about union of sets contained in other union of sets, that might be of independent interest. The second one uses a more graph-theoretical approach, by studying the properties of a maximum set of vertex-disjoint directed triangles.

Published
2010

12. First Order Properties on Nowhere Dense Structures

Author

Jaroslav Nešetřil, Patrice Ossona de Mendez, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Centre d'Analyse et de Mathématique sociales (CAMS), and École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, Finite model theory, Logic, Computer Science::Information Retrieval, The Intersect, Nowhere dense set, First order, Mathematical proof, Combinatorics, Philosophy, Corollary, Bounded function, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Homomorphism, Mathematics
Abstract

A set A of vertices of a graph G is called d-scattered in G if no two d-neighborhoods of (distinct) vertices of A intersect. In other words, A is d-scattered if no two distinct vertices of A have distance at most 2d. This notion was isolated in the context of finite model theory by Ajtai and Gurevich and recently it played a prominent role in the study of homomorphism preservation theorems for special classes of structures (such as minor closed classes). This in turn led to the notions of wide, almost wide and quasi-wide classes of graphs. It has been proved previously that minor closed classes and classes of graphs with locally forbidden minors are examples of such classes and thus (relativized) homomorphism preservation theorem holds for them. In this paper we show that (more general) classes with bounded expansion and (newly defined) classes with bounded local expansion and even (very general) nowhere dense classes are quasi wide. This not only strictly generalizes the previous results but it also provides new proofs and algorithms for some of the old results. It appears that bounded expansion and nowhere dense classes are perhaps a proper setting for investigation of wide-type classes as in several instances we obtain a structural characterization. This also puts classes of bounded expansion in the new context. Our motivation stems from finite dualities. As a corollary we obtain that any homomorphism closed first order definable property restricted to a bounded expansion class is a restricted duality.

Published
2010

13. Extremal problems for sparse graphs

Author

Jaroslav Nešetřil, Patrice Ossona de Mendez, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Centre d'Analyse et de Mathématique sociales (CAMS), École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS), and Ossona de Mendez, Patrice

Subjects
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Combinatorics, Random graph, Extremal combinatorics, Indifference graph, Dense graph, Chordal graph, Nowhere dense set, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Graph theory, Ramsey's theorem, Mathematics
Abstract

We survey some of the recent results related to the study of sparse graphs using the nowhere dense - somewhere dense dichotomy. Particularly we extend known results related to property testing, sublinear expanders, Ramsey numbers and FO model checking. All this is done under the same umbrella of nowhere dense and bounded expansion classes in many of their incarnations. We concentrate on extremal (mostly graph theory) results leaving algorithmic and structural aspects to other occasions.

Published
2010

14. A note on antisymmetric flows in graphs

Author

Daniel Král, Tomáš Kaiser, Jean-Sébastien Sereni, Zdenk Dvořák, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Katedra Matematiky - University of West Bohemia (KMA), University of West Bohemia [Plzeň ], Institut teoretické informatiky (ITI), Charles University [Prague] (CU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and European Project: 224548,EC:FP7:ICT,FP7-ICT-2007-2,AEOLUS(2008)

Subjects
Discrete mathematics, Antisymmetric relation, 010102 general mathematics, 0102 computer and information sciences, Nowhere-zero flow, Orientation (graph theory), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Theoretical Computer Science, 05C21, 05C15, Combinatorics, Flow (mathematics), Computational Theory and Mathematics, 010201 computation theory & mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology, 0101 mathematics, nowhere-zero flow, antisymmetric flow, Mathematics
Abstract

International audience; We prove that any orientation of a graph without bridges and directed 2-edge-cuts admits a (Z3^2 × Z9^3)-antisymmetric flow, which improves the bounds obtained by DeVos, Johnson and Seymour, and DeVos, Nesetril and Raspaud.

Published
2010

15. Almost All F-Free Graphs Have The Erdos-Hajnal Property

Author

Bruce Reed, Stéphan Thomassé, Martin Loebl, Alex Scott, Andrew Thomason, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Mathematical Institute [Oxford] (MI), University of Oxford, Statistical Laboratory [Cambridge], Department of Pure Mathematics and Mathematical Statistics (DPMMS), Faculty of mathematics Centre for Mathematical Sciences [Cambridge] (CMS), University of Cambridge [UK] (CAM)-University of Cambridge [UK] (CAM)-Faculty of mathematics Centre for Mathematical Sciences [Cambridge] (CMS), University of Cambridge [UK] (CAM)-University of Cambridge [UK] (CAM), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), University of Oxford [Oxford], Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), and École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
Discrete mathematics, 010102 general mathematics, Induced subgraph, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 16. Peace & justice, 01 natural sciences, Degeneracy (graph theory), Combinatorics, Rado graph, 010201 computation theory & mathematics, Graph power, Triangle-free graph, Split graph, 0101 mathematics, Forbidden graph characterization, Mathematics, Universal graph
Abstract

International audience; Erdős and Hajnal conjectured that, for every graph H, there exists a constant ɛ(H) > 0 such that every H-free graph G (that is, not containing H as an induced subgraph) must contain a clique or an independent set of size at least |G|ɛ( H). We prove that there exists ɛ(H) such that almost every H-ïvee graph G has this property, meaning that, amongst the if-free graphs with n vertices, the proportion having the property tends to one as n → ∞.

Published
2010

16. Identifying and locating-dominating codes in (random) geometric networks

Author

Tobias Müller, J.-s. Sereni, Centrum voor Wiskunde en Informatica (CWI), Centrum Wiskunde & Informatica (CWI)-Netherlands Organisation for Scientific Research, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Institut teoretické informatiky (ITI), Charles University [Prague] (CU), and Networks and Optimization

Subjects
Statistics and Probability, Dense graph, unit disk graph, 0102 computer and information sciences, 02 engineering and technology, locating-dominating code, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], random geometric graph, 01 natural sciences, Theoretical Computer Science, Combinatorics, Indifference graph, Pathwidth, identifying code, Chordal graph, Random regular graph, 0202 electrical engineering, electronic engineering, information engineering, Cograph, Mathematics, Random graph, Discrete mathematics, Applied Mathematics, 020206 networking & telecommunications, 1-planar graph, Computational Theory and Mathematics, 010201 computation theory & mathematics, ComputingMethodologies_DOCUMENTANDTEXTPROCESSING
Abstract

We model a problem about networks built from wireless devices using identifying and locating–dominating codes in unit disk graphs. It is known that minimizing the size of an identifying code is -complete even for bipartite graphs. First, we improve this result by showing that the problem remains -complete for bipartite planar unit disk graphs. Then, we address the question of the existence of an identifying code for random unit disk graphs. We derive the probability that there exists an identifying code as a function of the radius of the disks, and we find that for all interesting ranges of r this probability is bounded away from one. The results obtained are in sharp contrast to those concerning random graphs in the Erdős–Rényi model. Another well-studied class of codes is that of locating–dominating codes, which are less demanding than identifying codes. A locating–dominating code always exists, but minimizing its size is still -complete in general. We extend this result to our setting by showing that this question remains -complete for arbitrary planar unit disk graphs. Finally, we study the minimum size of such a code in random unit disk graphs, and we prove that with probability tending to one, it is of size (n/r)2/3+o(1) if r ≤ /2−ϵ is chosen such that nr2 → ∞, and of size n1+o(1) if nr2 ≪ lnn.

Published
2009

17. Fraternal augmentations, arrangeability and linear Ramsey numbers

Author

Jaroslav Nešetřil, Patrice Ossona de Mendez, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Centre d'Analyse et de Mathématique sociales (CAMS), and École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, Mathematics::Combinatorics, Conjecture, Ramsey theory, Theoretical Computer Science, Combinatorics, Computational Theory and Mathematics, Bounded function, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Bounded expansion, Discrete Mathematics and Combinatorics, Geometry and Topology, Ramsey's theorem, Chromatic scale, Mathematics
Abstract

International audience; We relate the notions of arrangeability and admissibility to bounded expansion classes and prove that these notions can be characterized by nabla_1(G). (The Burr–Erdős conjecture relates to nabla_0(G).) This implies the linearity of the Ramsey number and the bounded game chromatic number for some new classes of graphs.

Published
2009

18. Sort and search: Exact algorithms for generalized domination

Author

Jan Kratochvíl, Petr A. Golovach, Mathieu Liedloff, Fedor V. Fomin, Dieter Kratsch, Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'Informatique Théorique et Appliquée (LITA), Université de Lorraine (UL), Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), and Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO)

Subjects
Vertex (graph theory), Infinite set, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, 16. Peace & justice, 01 natural sciences, Computer Science Applications, Theoretical Computer Science, Combinatorics, Integer, 010201 computation theory & mathematics, Dominating set, Signal Processing, 0202 electrical engineering, electronic engineering, information engineering, sort, Graph algorithms, Invariant (mathematics), Undirected graph, Algorithm, Information Systems, Mathematics
Abstract

International audience; In 1994, Telle introduced the following notion of domination, which generalizes many domination-type graph invariants. Let $\sigma$ and $\varrho$ be two sets of non negative integers. A vertex subset $S\subseteq V$ of an undirected graph $G=(V,E)$ is called a $(\sigma,\varrho)$-dominating set of $G$ if $|N(v)\cap S| \in \sigma$ for all $v\in S$ and $|N(v)\cap S| \in \varrho$ for all $v\in V\setminus S$. In this paper, we prove that decision, optimization, and counting variants of $(\{p\},\{q\})$-domination are solvable in time $2^{|V|/2}\cdot |V|^{O(1)}$. We also show how to extend these results for infinite $\sigma=\{p+m\cdot \ell\colon \ell\in \mathbb{N}_0\}$ and $\varrho=\{q+m\cdot \ell \colon \ell\in \mathbb{N}_0\}$. For the case $|\sigma|+|\varrho|=3$, these problems can be solved in time $3^{|V|/2}\cdot|V|^{O(1)}$, and similarly to the case $|\sigma|=|\varrho|=1$ it is possible to extend the algorithm for some infinite sets.

Published
2009

19. A step toward the Bermond-Thomassen conjecture about disjoint cycles in digraphs

Author

Nicolas Lichiardopol, Jean-Sébastien Sereni, Attila Pór, Lycée Adam de Craponne, Department of Mathematics - Western Kentucky University (WKU), Western Kentucky University (WKU), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), and Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, 021103 operations research, Conjecture, General Mathematics, 0211 other engineering and technologies, Out degree, disjoint cycles, Digraph, 0102 computer and information sciences, 02 engineering and technology, Disjoint sets, out-degree, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, digraph, Combinatorics, 010201 computation theory & mathematics, Bermond-Thomassen conjecture, 05C20, Mathematics
Abstract

International audience; In 1981, Bermond and Thomassen conjectured that every digraph with minimum out-degree at least 2k-1 contains k disjoint cycles. This conjecture is trivial for k=1, and was established for k=2 by Thomassen in 1983. We verify it for the next case, proving that every digraph with minimum out-degree at least five contains three disjoint cycles. To show this, we improve Thomassen's result by proving that every digraph whose vertices have out-degree at least three, except at most two with out-degree two, indeed contains two disjoint cycles.

Published
2009

20. Reconfiguration of the Routing in WDM Networks with Two Classes of Services

Author

Coudert, David, Huc, Florian, Mazauric, Dorian, Nisse, Nicolas, Sereni, Jean-Sébastien, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)

Subjects
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]
Abstract

International audience; In WDM backbone networks, the traffic pattern evolves constantly due to the nature of the demand itself or because of equipment failures leading to reroute affected connections. In this context, requests are routed greedily using available resources without changing the routing of pre-established connections. However, such a policy leads to a poor usage of resources and so higher blocking probability: new connection requests might be rejected while network resources are sufficient to serve all the traffic. Therefore, it is important to regularly reconfigure the network by rerouting established connections in order to optimize the usage of network resources. In this paper, we consider the network reconfiguration problem that consists in switching existing connections one after the other from the current routing to a new pre-computed routing. Due to cyclic dependencies between connections, some requests may have to be temporarily interrupted during this process. Clearly, the number of requests simultaneously interrupted has to be minimized. Furthermore, it might be impossible for the network operator to interrupt some connections because of the contract signed with the corresponding clients. In this setting, the network reconfiguration problem consists in going from a routing to another one given that some priority connections cannot be interrupted. The network reconfiguration problem without priority connections has previously been modeled as a cops-and-robber game. Here, we first extend this model to handle priority connections. Then we identify cases where no solution exists. Using a simple transformation, we prove that the reconfiguration problem with priority connections can be reduced to the problem without this constraint. Finally, we propose a new heuristic algorithm that improves upon previous proposals.

Published
2009

21. Improper Colouring of Unit Disk Graphs

Author

Havet, Frédéric, Kang, Ross, Sereni, Jean-Sébastien, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Statistics [Oxford], University of Oxford, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), and University of Oxford [Oxford]

Subjects
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2009

22. Circular choosability

Author

Havet, F., Kang, Ross, Müller, Tobias, Sereni, J.-S., Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Statistics [Oxford], University of Oxford, Centrum voor Wiskunde en Informatica (CWI), Centrum Wiskunde & Informatica (CWI)-Netherlands Organisation for Scientific Research, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), This work was partially supported by Region Provence-Alpes-Cote d'Azur, and the European project ist fet Aeolus., Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), University of Oxford [Oxford], and Networks and Optimization

Subjects
010201 computation theory & mathematics, 010102 general mathematics, Discrete Mathematics and Combinatorics, 0102 computer and information sciences, Geometry and Topology, 0101 mathematics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences
Abstract

International audience; We study circular choosability, a notion recently introduced by Mohar and by Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that cch(G) = O(ch(G) + ln |V(G)|) for every graph G. We investigate a generalisation of circular choosability, the circular f-choosability, where f is a function of the degrees. We also consider the circular choice number of planar graphs. Mohar asked for the value of τ := sup {cch(G) : G is planar}, and we prove that 68, thereby providing a negative answer to another question of Mohar. We also study the circular choice number of planar and outerplanar graphs with prescribed girth, and graphs with bounded density.

Published
2009

23. About a Brooks-type theorem for improper colouring

Author

RICARDO CORRÊA, Havet, F., Sereni, J. -S, Departamento do Computacao [Fortaleza BR], Universidade Federal do Ceará = Federal University of Ceará (UFC), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)

Subjects
Brooks, 05C15, defective colouring, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], complexity, improper colouring
Abstract

International audience; A graph is k-improperly -colourable if its vertices can be partitioned into parts such that each part induces a subgraph of maximum degree at most k. A result of Lovasz a states that for any graph G, such a partition exists if l is at least (Δ(G)+1)/(k+1) . When k = 0, this bound can be reduced by Brooks' Theorem, unless G is complete or an odd cycle. We study the following question, which can be seen as a generalisation of the celebrated Brooks' Theorem to improper colouring: does there exist a polynomial-time algorithm that decides whether a graph G of maximum degree Δ has k-improper chromatic number at most (Δ+1)/(k+1) - 1? We show that the answer is no, unless P = N P , when Δ= (k + 1)l, k>0 and l+√l < 2k + 4. We also show that, if G is planar, k = 1 or k = 2, Δ = 2k + 2, and l= 2, then the answer is still no, unless P = N P . These results answer some questions of Cowen et al. [Journal of Graph Theory 24(3):205-219, 1997].

Published
2009

24. Lower bounding the boundary of a graph in terms of its maximum or minimum degree

Author

Jean-Sébastien Sereni, Tobias Müller, Attila Pór, Centrum voor Wiskunde en Informatica (CWI), Centrum Wiskunde & Informatica (CWI)-Netherlands Organisation for Scientific Research, Department of Mathematics - Western Kentucky University (WKU), Western Kentucky University (WKU), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and Eurandom

Subjects
Discrete mathematics, Vertex (graph theory), 021103 operations research, Degree (graph theory), Distance, Boundary, 0211 other engineering and technologies, Neighbourhood (graph theory), 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Boundary vertex, Theoretical Computer Science, Combinatorics, Circulant graph, 010201 computation theory & mathematics, Graph power, Bipartite graph, Discrete Mathematics and Combinatorics, Bound graph, Regular graph, Mathematics
Abstract

International audience; A vertex v of a graph G is a boundary vertex if there exists a vertex u such that the distance in G from u to v is at least the distance from u to any neighbour of v. We give the best possible lower bound, up to a constant factor, on the number of boundary vertices of a graph in terms of its minimum degree (or maximum degree). This settles a problem introduced by Hasegawa and Saito.

Published
2008

25. Exact algorithms for $L(2,1)$-labeling of graphs

Author

Havet, Frédéric, Klazar, Martin, Kratochvil, Jan, Kratsch, Dieter, Liedloff, Matthieu, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'Informatique Théorique et Appliquée (LITA), Université de Lorraine (UL), INRIA, Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)

Subjects
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph $G=(V,E)$ into an interval of integers $\{0, \dots ,k\}$ is an $L(2,1)$-labeling of $G$ of span $k$ if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed $k\ge 4$, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive $O((k+1)^n)$ algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of $k=4$ -- here the running time of our algorithm is $O(1.3006^n)$. % $O(1.3161^n)$. Furthermore we show that dynamic programming can be used to establish %an $O(c^n)$ algorithm to compute an optimal $L(2,1)$-labeling, for a constant $c< 4$. an $O(3.8730^n)$ algorithm to compute an optimal $L(2,1)$-labeling.

Published
2008

26. Branch and Recharge: Exact algorithms for generalized domination

Author

Jan Kratochvíl, Petr A. Golovach, Fedor V. Fomin, Dieter Kratsch, Mathieu Liedloff, Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'Informatique Théorique et Appliquée (LITA), Université de Lorraine (UL), School of Engineering and Computing Sciences, Durham University, Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), and Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO)

Subjects
Vertex (graph theory), General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Upper and lower bounds, Combinatorics, 0202 electrical engineering, electronic engineering, information engineering, Graph property, Undirected graph, General algorithm, PSPACE, Mathematics, Discrete mathematics, Applied Mathematics, Integer sequence, Graph, Search tree, Computer Science Applications, Exact algorithm, 010201 computation theory & mathematics, Theory of computation, Graph (abstract data type), 020201 artificial intelligence & image processing, NP-complete, Algorithm
Abstract

International audience; Let $\sigma$ and $\varrho$ be two sets of nonnegative integers. A vertex subset $S\subseteq V$ of an undirected graph $G=(V,E)$ is called a $(\sigma,\varrho)$-dominating set of $G$ if $|N(v)\cap S| \in \sigma$ for all $v\in S$ and $|N(v)\cap S| \in \varrho$ for all $v\in V\setminus S$. This notion introduced by Telle generalizes many domination-type graph invariants. For many particular choices of $\sigma$ and $\varrho$ it is NP-complete to decide whether an input graph has a $(\sigma,\varrho)$-dominating set. We show a general algorithm enumerating all $(\sigma,\varrho)$-dominating sets of an input graph $G$ in time $O^*(c^n)$ for some $c

Published
2007

27. Competition of magnetic and hydrodynamic forces on ellipsoidal particles under shear: Influence of the Earth's magnetic field on particle alignment in viscous media

Author

Jezek, Josef, Gilder, Stuart A., Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Institut de Physique du Globe de Paris (IPGP), Centre National de la Recherche Scientifique (CNRS)-Université de La Réunion (UR)-Université Paris Diderot - Paris 7 (UPD7)-IPG PARIS-Institut national des sciences de l'Univers (INSU - CNRS), Department of Earth and Environmental Sciences [Munich], Ludwig-Maximilians-Universität München (LMU), Department of Earth and Environmental Sciences [München], and Institut national des sciences de l'Univers (INSU - CNRS)-IPG PARIS-Université Paris Diderot - Paris 7 (UPD7)-Université de La Réunion (UR)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[SDU]Sciences of the Universe [physics]
Abstract

International audience; [1] We present a model that describes the rotation of ellipsoidal magnetic particles in a viscous fluid under the influence of hydrodynamic and magnetic forces, with an aim to better understand how sediments acquire their remanent magnetizations. Analyses of the governing equations elucidate how magnetic particles will rotate for different values of leading parameters including particle shape, remanent and induced magnetic intensity, magnetic field intensity and direction, strain rate, shear direction, and viscosity. Numerical solution of the governing equations makes it possible to visualize the rotation path and the magnetic direction of a particle through time. Thus the model can discern the timescales and trajectories of magnetic particles rotating due to torque of the magnetic field couple while simultaneously entrained in a velocity gradient. For example, in a layer of viscosity 10 4 Pa s, prolate magnetite starting at any initial orientation and subjected to simple shear with a strain rate of 3.17 Â 10 À8 s À1 needs 4 months to rotate within 3° of the Earth's field direction. Under the same conditions, hydrodynamic forces will govern the orientation of oblate hematite whose moment will be perpetually randomly oriented with respect to the magnetic field direction. When applied to laboratory experiments, the viscous model successfully matches the observed data, particularly after accounting for mechanical interaction and flocculation effects. Magnetic anisotropies calculated from multiparticle systems of hematite yield typical sedimentary fabrics with relatively low percentages of anisotropy (

Published
2006

28. On edge-maps whose inverse preserves flows or tensions

Author

André Raspaud, Matt DeVos, Jaroslav Nešetřil, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Raspaud, André

Subjects
Vertex (graph theory), Conjecture, 010102 general mathematics, Inverse, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Graph, Edge maps, Combinatorics, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], 010201 computation theory & mathematics, Petersen graph, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract

A cycle of a graph G is a set C ⊑ E(G) so that every vertex of the graph (V (G), C) has even degree. If G,H are graphs, we define a map φ: E(G) → E(H) to be cycle-continuous if the pre-image of every cycle of H is a cycle of G. A fascinating conjecture of Jaeger asserts that every bridgeless graph has a cycle-continuous mapping to the Petersen graph. Jaeger showed that if this conjecture is true, then so is the 5-cycle-double-cover conjecture and the Fulkerson conjecture.

Published
2006

29. Linear time low tree-width partitions and algorithmic consequences

Author

Jaroslav Nešetřil, Patrice Ossona de Mendez, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Centre d'Analyse et de Mathématique sociales (CAMS), École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS), and Ossona de Mendez, Patrice

Subjects
Discrete mathematics, Vertex (graph theory), Subgraph isomorphism problem, Treewidth, Combinatorics, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Bounded function, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Graph minor, Induced subgraph isomorphism problem, Graph homomorphism, Graph property, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

Classes of graphs with bounded expansion have been introduced in [15], [12]. They generalize both proper minor closed classes and classes with bounded degree.For any class with bounded expansion C and any integer p there exists a constant N(C,p) so that the vertex set of any graph G ∈ C may be partitioned into at most N(C,p) parts, any i ≤ p parts of them induce a subgraph of tree-width at most (i-1) [12] (actually, of tree-depth [16] at most i, what is sensibly stronger). Such partitions are central to the resolution of homomorphism problems like restricted homomorphism dualities [14].We give here a simple algorithm to compute such partitions and prove that if we restrict the input graph to some fixed class C with bounded expansion, the running time of the algorithm is bounded by a linear function of the order of the graph (for fixed C and p).This result is applied to get a linear time algorithm for the subgraph isomorphism problem with fixed pattern and input graphs in a fixed class with bounded expansion.More generally, let φ be a first order logic sentence. We prove that any fixed graph property of type "∃X: (|X| ≤ p) ⇿(G[X]=φ)" may be decided in linear time for input graphs in a fixed class with bounded expansion.

Published
2006

30. Folding

Author

Patrice Ossona de Mendez, Jaroslav Nesetril, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Centre d'Analyse et de Mathématique sociales (CAMS), and École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)

Subjects
homomorphism, 05C15, Computational Theory and Mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, constrained orientation, Theoretical Computer Science
Abstract

We define folding of a directed graph as a coloring (or a homomorphism) which is injective on all the down sets of a given depth. While in general foldings are as complicated as homomorphisms for some some classes they present an useful tool to study colorings and homomorphisms. Our main result yields for any proper minor closed class C a folding (of any prescribed depth) using a fixed number of colors. This in turn yields (for any C) the existence of a Kk-free graph which bounds all Kk-free graphs belonging to C. This has been conjectured and solved for k=3. Particularly, we prove (without using 4CT) the existence of a graph H with chromatic number at most 5 and clique number at most 4, such that any planar graph G is homomorphic to H. This is sandwiched between 4CT and 5CT for planar graphs and the general case has bearing to Hadwiger Conjecture.

Published
2006

31. The grad of a graph and classes with bounded expansion

Author

Jaroslav Nešetřil, Patrice Ossona de Mendez, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Centre d'Analyse et de Mathématique sociales (CAMS), École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS), and André Raspaud and Olivier Delmas

Subjects
Combinatorics, Discrete mathematics, Applied Mathematics, Bounded function, Bounded expansion, Discrete Mathematics and Combinatorics, Homomorphism, Invariant (mathematics), Tree-depth, Graph, Mathematics
Abstract

We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ∇r(G). We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings and homomorphism dualities.

Published
2005

32. Grad and classes with bounded expansion III. restricted dualities

Author

Nesetril, Jaroslav, Ossona De Mendez, Patrice, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Centre d'Analyse et de Mathématique sociales (CAMS), and École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 05C75 05C78
Abstract

We study restricted homomorphism dualities in the context of classes with bounded expansion. This presents a generalization of restricted dualities obtained earlier for bounded degree graphs and also for proper minor closed classes. This is related to distance coloring of graphs and to the ''approximative version'' of Hadwiger conjecture.

Published
2005

33. On universal graphs for planar oriented graphs of a given girth

Author

Alexandr V. Kostochka, Jaroslav Nešetřil, Eric Sopena, Oleg V. Borodin, André Raspaud, Raspaud, André, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire Bordelais de Recherche en Informatique (LaBRI), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)

Subjects
Discrete mathematics, Symmetric graph, 010102 general mathematics, 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, 1-planar graph, Theoretical Computer Science, Combinatorics, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], 010201 computation theory & mathematics, Outerplanar graph, Triangle-free graph, Odd graph, Discrete Mathematics and Combinatorics, Graph homomorphism, 0101 mathematics, Pancyclic graph, Mathematics, Universal graph
Abstract

The oriented chromatic number o ( H ) of an oriented graph H is defined to be the minimum order of an oriented graph H ′ such that H has a homomorphism to H ′. If each graph in a class K has a homomorphism to the same H ′, then H ′ is K - universal . Let P k denote the class of orientations of planar graphs with girth at least k . Clearly, P 3 ⊃ P 4 ⊃ P 5 … We discuss the existence of P k -universal graphs with special properties. It is known (see Raspaud and Sopena, 1994) that there exists a P 3 -universal graph on 80 vertices. We prove here that 1. (1) there exist no planar P 4 -universal graphs; 2. (2) there exists a planar P 16 -universal graph on 6 vertices; 3. (3) for any k , there exist no planar P k -universal graphs of girth at least 6; 4. (4) for any k , there exists a P 40 k -universal graph of girth at least k + 1.

Published
1998

34. Les effets territoriaux de la transition politique et économique en République tchèque

Author

ILLNER , Michal, Viturka, Milan, Havlík, Václav, 'ubomír Falťan, L, Zubek, Leopold, Ježek, Josef, Maier, Karel, Czech Academy of Sciences [Prague] (CAS), Masaryk University [Brno] (MUNI), CENTRUM HALOVÝCH SPORTŮ, Slovak Academy of Sciences (SAS), International Commission for the Protection of the Odra River, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, and Faculty of Architecture, Prague

Subjects
[SHS.ARCHI]Humanities and Social Sciences/Architecture, space management, conséquences territoriales de la transition politique et économique post-communiste, [SHS.SOCIO]Humanities and Social Sciences/Sociology, aspects territoriaux de la transition, développement du marché du travail dans les sociétés post-communistes, [SHS.ECO]Humanities and Social Sciences/Economics and Finance, [SHS.SCIPO]Humanities and Social Sciences/Political science, planification territoriale et urbanisme post-communistes
Abstract

International audience; Cette première table ronde a pour sujet les aspects territoriaux de la transition politique et économique en République tchèque. Un premier intervenant, M. Illner (AV ČR) s’intéresse à la dimension territoriale des changements sociaux induits par la transformation de la République tchèque dans la période post-communiste, puis M. Viturka (Masarykova Univerzita) se penche sur les facteurs de la différenciation régionale dans le développement du marché du travail en République tchèque. Václav Havlík analyse par la suite le statut actuel de la planification territoriale et de l’urbanisme dans une jeune économie de marché, tandis que Ľubomír Falťan (SAS) replace l’exemple de la Slovaquie dans un contexte plus largement centre-européen.

Published
1995

35. Les effets territoriaux de la transition politique et économique en République tchèque: Cahiers du CEFRES N° 9f, Territoires en mutation

Author

Michal Illner, Milan Viturka, Václav Havlík, L 'Ubomír Falťan, Leopold Zubek, Josef Ježek, Karel Maier, Czech Academy of Sciences [Prague] (CAS), Masaryk University [Brno] (MUNI), CENTRUM HALOVÝCH SPORTŮ, Slovak Academy of Sciences (SAS), International Commission for the Protection of the Odra River, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, and Faculty of Architecture, Prague

Subjects
[SHS.ARCHI]Humanities and Social Sciences/Architecture, space management, conséquences territoriales de la transition politique et économique post-communiste, [SHS.SOCIO]Humanities and Social Sciences/Sociology, aspects territoriaux de la transition, aspects territoriaux de la transition , conséquences territoriales de la transition politique et économique post-communiste , développement du marché du travail dans les sociétés post-communistes , planification territoriale et urbanisme post-communistes, développement du marché du travail dans les sociétés post-communistes, [SHS.ECO]Humanities and Social Sciences/Economics and Finance, [SHS.SCIPO]Humanities and Social Sciences/Political science, planification territoriale et urbanisme post-communistes
Abstract

International audience; Cette première table ronde a pour sujet les aspects territoriaux de la transition politique et économique en République tchèque. Un premier intervenant, M. Illner (AV ČR) s’intéresse à la dimension territoriale des changements sociaux induits par la transformation de la République tchèque dans la période post-communiste, puis M. Viturka (Masarykova Univerzita) se penche sur les facteurs de la différenciation régionale dans le développement du marché du travail en République tchèque. Václav Havlík analyse par la suite le statut actuel de la planification territoriale et de l’urbanisme dans une jeune économie de marché, tandis que Ľubomír Falťan (SAS) replace l’exemple de la Slovaquie dans un contexte plus largement centre-européen.

Published
1995

36. Les effets territoriaux de la transition politique et économique en République tchèque

Author

Illner, Michal, Viturka, Milan, Havlík, Václav, 'Ubomír Falťan, L, Zubek, Leopold, Ježek, Josef, Maier, Karel, Madl, Claire, Czech Academy of Sciences [Prague] (CAS), Masaryk University [Brno] (MUNI), CENTRUM HALOVÝCH SPORTŮ, Slovak Academy of Sciences (SAS), International Commission for the Protection of the Odra River, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, and Faculty of Architecture, Prague

Subjects
[SHS.ARCHI]Humanities and Social Sciences/Architecture, space management, conséquences territoriales de la transition politique et économique post-communiste, [SHS.SOCIO]Humanities and Social Sciences/Sociology, [SHS.SOCIO] Humanities and Social Sciences/Sociology, aspects territoriaux de la transition, développement du marché du travail dans les sociétés post-communistes, [SHS.ARCHI] Humanities and Social Sciences/Architecture, space management, [SHS.ECO] Humanities and Social Sciences/Economics and Finance, [SHS.ECO]Humanities and Social Sciences/Economics and Finance, [SHS.SCIPO] Humanities and Social Sciences/Political science, [SHS.SCIPO]Humanities and Social Sciences/Political science, planification territoriale et urbanisme post-communistes
Abstract

International audience; Cette première table ronde a pour sujet les aspects territoriaux de la transition politique et économique en République tchèque. Un premier intervenant, M. Illner (AV ČR) s’intéresse à la dimension territoriale des changements sociaux induits par la transformation de la République tchèque dans la période post-communiste, puis M. Viturka (Masarykova Univerzita) se penche sur les facteurs de la différenciation régionale dans le développement du marché du travail en République tchèque. Václav Havlík analyse par la suite le statut actuel de la planification territoriale et de l’urbanisme dans une jeune économie de marché, tandis que Ľubomír Falťan (SAS) replace l’exemple de la Slovaquie dans un contexte plus largement centre-européen.

Published
1995

Catalog

Books, media, physical & digital resources
See catalog results