Search

Your search keyword '"Thomas Bellitto"' showing total 8 results
Start Over Author "Thomas Bellitto" Topic mathematics - combinatorics
8 results on '"Thomas Bellitto"'

1. Homomorphically Full Oriented Graphs

Author

Thomas Bellitto, Christopher Duffy, and Gary MacGillivray

Subjects
computer science - discrete mathematics, mathematics - combinatorics, 05c60, 05c20, 68q17, Mathematics, QA1-939
Abstract

Homomorphically full graphs are those for which every homomorphic image is isomorphic to a subgraph. We extend the definition of homomorphically full to oriented graphs in two different ways. For the first of these, we show that homomorphically full oriented graphs arise as quasi-transitive orientations of homomorphically full graphs. This in turn yields an efficient recognition and construction algorithms for these homomorphically full oriented graphs. For the second one, we show that the related recognition problem is GI-hard, and that the problem of deciding if a graph admits a homomorphically full orientation is NP-complete. In doing so we show the problem of deciding if two given oriented cliques are isomorphic is GI-complete.

Published
2023
Full Text
View/download PDF

2. On the density of sets of the Euclidean plane avoiding distance 1

Author

Thomas Bellitto, Arnaud Pêcher, and Antoine Sédillot

Subjects
mathematics - metric geometry, computer science - discrete mathematics, mathematics - combinatorics, Mathematics, QA1-939
Abstract

A subset $A \subset \mathbb R^2$ is said to avoid distance $1$ if: $\forall x,y \in A, \left\| x-y \right\|_2 \neq 1.$ In this paper we study the number $m_1(\mathbb R^2)$ which is the supremum of the upper densities of measurable sets avoiding distance 1 in the Euclidean plane. Intuitively, $m_1(\mathbb R^2)$ represents the highest proportion of the plane that can be filled by a set avoiding distance 1. This parameter is related to the fractional chromatic number $\chi_f(\mathbb R^2)$ of the plane. We establish that $m_1(\mathbb R^2) \leq 0.25647$ and $\chi_f(\mathbb R^2) \geq 3.8991$.

Published
2021
Full Text
View/download PDF

3. Complexity of locally-injective homomorphisms to tournaments

Author

Stefan Bard, Thomas Bellitto, Christopher Duffy, Gary MacGillivray, and Feiran Yang

Subjects
computer science - discrete mathematics, mathematics - combinatorics, 05c15, Mathematics, QA1-939
Abstract

For oriented graphs $G$ and $H$, a homomorphism $f: G \rightarrow H$ is locally-injective if, for every $v \in V(G)$, it is injective when restricted to some combination of the in-neighbourhood and out-neighbourhood of $v$. Two of the possible definitions of local-injectivity are examined. In each case it is shown that the associated homomorphism problem is NP-complete when $H$ is a reflexive tournament on three or more vertices with a loop at every vertex, and solvable in polynomial time when $H$ is a reflexive tournament on two or fewer vertices.

Published
2018
Full Text
View/download PDF

4. On Supereulerian 2-Edge-Coloured Graphs

Author

Thomas Bellitto, Anders Yeo, and Jørgen Bang-Jensen

Subjects
Generalization, 0102 computer and information sciences, Edge (geometry), 01 natural sciences, Complete bipartite graph, Theoretical Computer Science, 05C38, 05C45, Combinatorics, symbols.namesake, Alternating hamiltonian cycle, FOS: Mathematics, Mathematics - Combinatorics, Discrete Mathematics and Combinatorics, 0101 mathematics, Mathematics, 010102 general mathematics, Eulerian path, Alternating cycle, Graph, Vertex (geometry), Multipartite, Cover (topology), Supereulerian, 010201 computation theory & mathematics, Eulerian factor, symbols, Combinatorics (math.CO), 2-edge-coloured graph, Extension of a 2-edge-coloured graph
Abstract

A 2-edge-coloured graph G is supereulerian if G contains a spanning closed trail in which the edges alternate in colours. We show that for general 2-edge-coloured graphs it is NP-complete to decide whether the graph is supereulerian. An eulerian factor of a 2-edge-coloured graph is a collection of vertex-disjoint induced subgraphs which cover all the vertices of G such that each of these subgraphs is supereulerian. We give a polynomial algorithm to test whether a 2-edge-coloured graph has an eulerian factor and to produce one when it exists. A 2-edge-coloured graph is (trail-)colour-connected if it contains a pair of alternating (u, v)-paths ((u, v)-trails) whose union is an alternating closed walk for every pair of distinct vertices u, v. We prove that a 2-edge-coloured complete bipartite graph is supereulerian if and only if it is colour-connected and has an eulerian factor. A 2-edge-coloured graph is M-closed if xz is an edge of G whenever some vertex u is joined to both x and z by edges of the same colour. M-closed 2-edge-coloured graphs, introduced in Contreras-Balbuena et al. (Discret Math Theoret Comput Sci 21:1, 2019), form a rich generalization of 2-edge-coloured complete graphs. We show that if G is obtained from an M-closed 2-edge-coloured graph H by substituting independent sets for the vertices of H, then G is supereulerian if and only if G is trail-colour-connected and has an eulerian factor. Finally we discuss 2-edge-coloured complete multipartite graphs and show that such a graph may not be supereulerian even if it is trail-colour-connected and has an eulerian factor.

Published
2021

5. Counterexamples to Thomassen’s Conjecture on Decomposition of Cubic Graphs

Author

Tereza Klimošová, Thomas Bellitto, Martin Merker, Yelena Yuditsky, and Marcin Witkowski

Subjects
Thomassen’s conjecture, 0211 other engineering and technologies, Graph decomposition, 0102 computer and information sciences, 02 engineering and technology, Astrophysics::Cosmology and Extragalactic Astrophysics, 01 natural sciences, Theoretical Computer Science, Combinatorics, Computer Science::Discrete Mathematics, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Astrophysics::Solar and Stellar Astrophysics, Astrophysics::Galaxy Astrophysics, Mathematics, Conjecture, Mathematics::Combinatorics, Degree (graph theory), 021107 urban & regional planning, 010201 computation theory & mathematics, Path (graph theory), Cubic graph, Combinatorics (math.CO), Cubic graphs, Counterexample
Abstract

We construct an infinite family of counterexamples to Thomassen’s conjecture that the vertices of every 3-connected, cubic graph on at least 8 vertices can be colored blue and red such that the blue subgraph has maximum degree at most 1 and the red subgraph minimum degree at least 1 and contains no path on 4 vertices.

Published
2021

6. Proper-walk connection number of graphs

Author

Jørgen Bang-Jensen, Anders Yeo, and Thomas Bellitto

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Existential quantification, Data_MISCELLANEOUS, connecting edge-colouring, 0102 computer and information sciences, Characterization (mathematics), 01 natural sciences, Combinatorics, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 0101 mathematics, Time complexity, Connectivity, Mathematics, 010102 general mathematics, proper connection by walks, Graph, 010201 computation theory & mathematics, connected graph, Connection number, strongly connected digraph, Geometry and Topology, Combinatorics (math.CO), Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

This paper studies the problem of proper-walk connection number: given an undirected connected graph, our aim is to colour its edges with as few colours as possible so that there exists a properly coloured walk between every pair of vertices of the graph i.e. a walk that does not use consecutively two edges of the same colour. The problem was already solved on several classes of graphs but still open in the general case. We establish that the problem can always be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be properly connected with $k$ colours for every possible value of $k$., Comment: 25 pages, 9 figures

Published
2019
Full Text
View/download PDF

7. On Minimum Connecting Transition Sets in Graphs

Author

Thomas Bellitto, Benjamin Bergougnoux, Bergougnoux, Benjamin, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, Vertex (graph theory), Discrete Mathematics (cs.DM), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 010102 general mathematics, Approximation algorithm, Unordered pair, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 01 natural sciences, Graph, Combinatorics, 010201 computation theory & mathematics, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), 0101 mathematics, Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract

A forbidden transition graph is a graph defined together with a set of permitted transitions i.e. unordered pair of adjacent edges that one may use consecutively in a walk in the graph. In this paper, we look for the smallest set of transitions needed to be able to go from any vertex of the given graph to any other. We prove that this problem is NP-hard and study approximation algorithms. We develop theoretical tools that help to study this problem.

Published
2018

8. On the density of sets avoiding parallelohedron distance 1

Author

Arnaud Pêcher, Philippe Moustrou, Christine Bachoc, Thomas Bellitto, Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Reformulations based algorithms for Combinatorial Optimization (Realopt), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), This study has been carried out with financial support from the French State, managed by the French National Research Agency (ANR) in the frame of the 'Investments for the future' Programme IdEx Bordeaux - CPU (ANR-10-IDEX-03-02), ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, and IdEx Bordeaux - CPU

Subjects
050101 languages & linguistics, Parallelohedron, [SHS.INFO]Humanities and Social Sciences/Library and information sciences, Dimension (graph theory), 1991Mathematics Subject Classification.52C10, 52B11, 11H06, Polytope, 02 engineering and technology, Space (mathematics), Theoretical Computer Science, Combinatorics, Mathematics - Metric Geometry, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, 52C10, 52B11, 11H06, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 0501 psychology and cognitive sciences, [MATH.MATH-MG]Mathematics [math]/Metric Geometry [math.MG], Mathematics, chromatic numbers, 05 social sciences, Chromatic number, Metric Geometry (math.MG), Distance graphs, Lattices, Euclidean distance, Computational Theory and Mathematics, Parallelohedra, 020201 artificial intelligence & image processing, Geometry and Topology, Combinatorics (math.CO), Voronoi diagram
Abstract

The maximal density of a measurable subset of $${{\mathbb {R}}}^n$$ avoiding Euclidean distance 1 is unknown except in the trivial case of dimension 1. In this paper, we consider the case of a distance associated to a polytope that tiles space, where it is likely that the sets avoiding distance 1 are of maximal density $$2^{-n}$$ , as conjectured by Bachoc and Robins. We prove that this is true for $$n=2$$ , and for the Voronoi regions of the lattices $$A_n$$ , $$n\ge 2$$ .

Published
2017
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results