The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Stéphan Thomassé - One of the best experts on this subject based on the ideXlab platform.
-
Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
Combinatorica, 2019Co-Authors: Julien Bensmail, Ararat Harutyunyan, Stéphan ThomasséAbstract:In 2006, Barát and Thomassen conjectured that there is a function f such that, for every fixed tree T with t edges, every f(t)-edge-connected graph with its number of edges divisible by t has a partition of its edges into copies of T. This conjecture was recently verified by the current authors and Merker. We here further focus on the path case of the Barát-Thomassen conjecture. Before the aforementioned general proof was announced, several successive steps towards the path case of the conjecture were made, notably by Thomassen, until this particular case was totally solved by Botler, Mota, Oshiro and Wakabayashi. Our goal in this paper is to propose an alternative proof of the path case with a weaker hypothesis: Namely, we prove that there is a function f such that every 24-edge-connected graph with minimum degree f(t) has an edge-partition into paths of length t whenever t divides the number of edges. We also show that 24 can be dropped to 4 when the graph is eulerian.
-
a proof of the barat Thomassen conjecture
arXiv e-prints, 2016Co-Authors: Julien Bensmail, Ararat Harutyunyan, Martin Merker, Stéphan ThomasséAbstract:The Barat-Thomassen conjecture asserts that for every tree T on m edges, there exists a constant k T such that every k T-edge-connected graph with size divisible by m can be edge-decomposed into copies of T. So far this conjecture has only been verified when T is a path or when T has diameter at most 4. Here we prove the full statement of the conjecture.
-
a proof of the bar at Thomassen conjecture
arXiv: Combinatorics, 2016Co-Authors: Julien Bensmail, Ararat Harutyunyan, Martin Merker, Stéphan ThomasséAbstract:The Barat-Thomassen conjecture asserts that for every tree $T$ on $m$ edges, there exists a constant $k_T$ such that every $k_T$-edge-connected graph with size divisible by $m$ can be edge-decomposed into copies of $T$. So far this conjecture has only been verified when $T$ is a path or when $T$ has diameter at most 4. Here we prove the full statement of the conjecture.
-
edge partitioning a graph into paths beyond the bar at Thomassen conjecture
arXiv: Combinatorics, 2015Co-Authors: Julien Bensmail, Ararat Harutyunyan, Tiennam Le, Stéphan ThomasséAbstract:The Barat-Thomassen conjecture asserts that there is a function $f$ such that for every fixed tree $T$ with $t$ edges, every graph which is $f(t)$-edge-connected with its number of edges divisible by $t$ has a partition of its edges into copies of $T$. This has been proved in the case of paths of length $2^k$ by Thomassen, and recently shown to be true for all paths by Botler, Mota, Oshiro and Wakabayashi. Our goal in this paper is to propose an alternative proof of the path case with a weaker hypothesis: Namely, we prove that there is a function $f$ such that every $24$-edge-connected graph with minimum degree $f(t)$ has an edge-partition into paths of length $t$ whenever $t$ divides the number of edges. We also show that $24$ can be dropped to $4$ when the graph is eulerian.
-
disjoint 3 cycles in tournaments a proof of the bermond Thomassen conjecture for tournaments
Journal of Graph Theory, 2014Co-Authors: Jorgen Bangjensen, Stephane Bessy, Stéphan ThomasséAbstract:We prove that every tournament with minimum out-degree at least inline image contains k disjoint 3-cycles. This provides additional support for the conjecture by Bermond and Thomassen that every digraph D of minimum out-degree inline image contains k vertex disjoint cycles. We also prove that for every inline image, when k is large enough, every tournament with minimum out-degree at least inline image contains k disjoint cycles. The linear factor 1.5 is best possible as shown by the regular tournaments.
Jeansebastien Sereni - One of the best experts on this subject based on the ideXlab platform.
-
transversals of longest paths and cycles
SIAM Journal on Discrete Mathematics, 2014Co-Authors: Dieter Rautenbach, Jeansebastien SereniAbstract:Let $G$ be a graph of order $n$. Let $\mathrm{lpt}(G)$ be the minimum cardinality of a set $X$ of vertices of $G$ such that $X$ intersects every longest path of $G$, and define $\mathrm{lct}(G)$ analogously for cycles instead of paths. We prove that $\mathrm{lpt}(G)\leqslant \lceil\frac{n}{4}-\frac{n^{2/3}}{90}\rceil$ if $G$ is connected, and $\mathrm{lct}(G)\leqslant \lceil\frac{n}{3}-\frac{n^{2/3}}{36}\rceil$ if $G$ is $2$-connected. Our bound on $\mathrm{lct}(G)$ improves an earlier result of Thomassen. Furthermore, we prove upper bounds on $\mathrm{lpt}(G)$ for planar graphs and graphs of bounded tree-width.
-
transversals of longest paths and cycles
arXiv: Combinatorics, 2013Co-Authors: Dieter Rautenbach, Jeansebastien SereniAbstract:Let G be a graph of order n. Let lpt(G) be the minimum cardinality of a set X of vertices of G such that X intersects every longest path of G and define lct(G) analogously for cycles instead of paths. We prove that lpt(G) \leq ceiling(n/4-n^{2/3}/90), if G is connected, lct(G) \leq ceiling(n/3-n^{2/3}/36), if G is 2-connected, and \lpt(G) \leq 3, if G is a connected circular arc graph. Our bound on lct(G) improves an earlier result of Thomassen and our bound for circular arc graphs relates to an earlier statement of Balister \emph{et al.} the argument of which contains a gap. Furthermore, we prove upper bounds on lpt(G) for planar graphs and graphs of bounded tree-width.
-
two proofs of the bermond Thomassen conjecture for tournaments with bounded minimum in degree
Discrete Mathematics, 2010Co-Authors: Stephane Bessy, Nicolas Lichiardopol, Jeansebastien SereniAbstract: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 tournaments. In the first proof, we prove auxiliary results about union of sets contained in another 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.
-
a step toward the bermond Thomassen conjecture about disjoint cycles in digraphs
SIAM Journal on Discrete Mathematics, 2009Co-Authors: Nicolas Lichiardopol, Attila Por, Jeansebastien SereniAbstract: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.
-
two proofs of bermond Thomassen conjecture for regular tournaments
Electronic Notes in Discrete Mathematics, 2007Co-Authors: Stephane Bessy, Nicolas Lichiardopol, Jeansebastien SereniAbstract:Abstract Bermond-Thomassen conjecture says that a digraph of minimum out-degree at least 2 r − 1 , r ⩾ 1 , contains at least r vertex-disjoint directed cycles. Thomassen proved that it is true when r = 2 , but 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 regular tournaments. In the first one, we shall 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.
Zdeněk Dvořak - One of the best experts on this subject based on the ideXlab platform.
-
a Thomassen type method for planar graph recoloring
European Journal of Combinatorics, 2021Co-Authors: Zdeněk Dvořak, Carl FeghaliAbstract:Abstract The reconfiguration graph R k ( G ) for the k -colorings of a graph G has as vertices all possible k -colorings of G and two colorings are adjacent if they differ in the color of exactly one vertex. A result of Bousquet and Perarnau (2016) regarding graphs of bounded degeneracy implies that for a planar graph G with n vertices, R 12 ( G ) has diameter at most 6 n , and if G is triangle-free, then R 8 ( G ) has diameter at most 4 n . We use a list coloring technique inspired by results of Thomassen to improve on the number of colors, showing that for a planar graph G with n vertices, R 10 ( G ) has diameter at most 8 n , and if G is triangle-free, then R 7 ( G ) has diameter at most 7 n .
-
a Thomassen type method for planar graph recoloring
arXiv: Combinatorics, 2020Co-Authors: Zdeněk Dvořak, Carl FeghaliAbstract:The reconfiguration graph $R_k(G)$ for the $k$-colorings of a graph $G$ has as vertices all possible $k$-colorings of $G$ and two colorings are adjacent if they differ in the color of exactly one vertex. We use a list coloring technique inspired by results of Thomassen to prove that for a planar graph $G$ with $n$ vertices, $R_{10}(G)$ has diameter at most $8n$, and if $G$ is triangle-free, then $R_7(G)$ has diameter at most $7n$.
-
three coloring triangle free planar graphs in linear time
Symposium on Discrete Algorithms, 2009Co-Authors: Zdeněk Dvořak, Ken-ichi Kawarabayashi, Robin ThomasAbstract:Grotzsch's theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms to find a 3-coloring, but it is not clear how to find such a coloring in linear time (Kowalik used a nontrivial data structure to construct an O(n log n) algorithm). We design a linear-time algorithm to find a 3-coloring of a given triangle-free planar graph. The algorithm avoids using any complex data structures, which makes it easy to implement. As a by-product we give a yet simpler proof of Grotzsch's theorem.
Robin Thomas - One of the best experts on this subject based on the ideXlab platform.
-
three coloring triangle free planar graphs in linear time
Symposium on Discrete Algorithms, 2009Co-Authors: Zdeněk Dvořak, Ken-ichi Kawarabayashi, Robin ThomasAbstract:Grotzsch's theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms to find a 3-coloring, but it is not clear how to find such a coloring in linear time (Kowalik used a nontrivial data structure to construct an O(n log n) algorithm). We design a linear-time algorithm to find a 3-coloring of a given triangle-free planar graph. The algorithm avoids using any complex data structures, which makes it easy to implement. As a by-product we give a yet simpler proof of Grotzsch's theorem.
-
six critical graphs on the klein bottle
Electronic Notes in Discrete Mathematics, 2008Co-Authors: Nathan Chenette, Luke Postle, Noah Streib, Carl Yerger, Robin Thomas, Daniel Kral, Jan Kyncl, Ken-ichi Kawarabayashi, Bernard LidickýAbstract:Abstract We exhibit an explicit list of nine graphs such that a graph drawn in the Klein bottle is 5-colorable if and only if it has no subgraph isomorphic to a member of the list. This answers a question of Thomassen [J. Comb. Theory Ser. B 70 (1997), 67–100] and implies an earlier result of Kral', Mohar, Nakamoto, Pangrac and Suzuki that an Eulerian triangulation of the Klein bottle is 5-colorable if and only if it has no complete subgraph on six vertices.
-
coloring even faced graphs in the torus and the klein bottle
Combinatorica, 2008Co-Authors: Daniel Kral, Robin ThomasAbstract:We prove that a triangle-free graph drawn in the torus with all faces bounded by even walks is 3-colorable if and only if it has no subgraph isomorphic to the Cayley graph C(Z 13; 1,5). We also prove that a non-bipartite quadrangulation of the Klein bottle is 3-colorable if and only if it has no non-contractible separating cycle of length at most four and no odd walk homotopic to a non-contractible two-sided simple closed curve. These results settle a conjecture of Thomassen and two conjectures of Archdeacon, Hutchinson, Nakamoto, Negami and Ota.
-
three coloring klein bottle graphs of girth five
Journal of Combinatorial Theory Series B, 2004Co-Authors: Robin Thomas, Barrett WallsAbstract:We prove that every graph of girth at least five which admits an embedding in the Klein bottle is 3-colorable. This solves a problem raised by Woodburn, and complements a result of Thomassen who proved the same for projective planar and toroidal graphs.
Ken-ichi Kawarabayashi - One of the best experts on this subject based on the ideXlab platform.
-
beyond the euler characteristic approximating the genus of general graphs
arXiv: Data Structures and Algorithms, 2014Co-Authors: Ken-ichi Kawarabayashi, Anastasios SidiropoulosAbstract:Computing the Euler genus of a graph is a fundamental problem in graph theory and topology. It has been shown to be NP-hard by [Thomassen '89] and a linear-time fixed-parameter algorithm has been obtained by [Mohar '99]. Despite extensive study, the approximability of the Euler genus remains wide open. While the existence of an $O(1)$-approximation is not ruled out, the currently best-known upper bound is a trivial $O(n/g)$-approximation that follows from bounds on the Euler characteristic. In this paper, we give the first non-trivial approximation algorithm for this problem. Specifically, we present a polynomial-time algorithm which given a graph $G$ of Euler genus $g$ outputs an embedding of $G$ into a surface of Euler genus $g^{O(1)}$. Combined with the above $O(n/g)$-approximation, our result also implies a $O(n^{1-\alpha})$-approximation, for some universal constant $\alpha>0$. Our approximation algorithm also has implications for the design of algorithms on graphs of small genus. Several of these algorithms require that an embedding of the graph into a surface of small genus is given as part of the input. Our result implies that many of these algorithms can be implemented even when the embedding of the input graph is unknown.
-
recognizing a totally odd k 4 subdivision parity 2 disjoint rooted paths and a parity cycle through specified elements
Symposium on Discrete Algorithms, 2010Co-Authors: Ken-ichi Kawarabayashi, Zhentao Li, Bruce ReedAbstract:A totally odd K4-subdivision is a subdivision of K4 where each subdivided edge has odd length. The recognition of a totally odd K4-subdivision plays an important role in both graph theory and combinatorial optimization. Sewell and Trotter [53], Zang [63] and Thomassen [60] independently conjectured the existence of a polynomial time recognition algorithm. In this paper, we give the first polynomial time algorithm for solving this problem. We also study the the parity two disjoint rooted paths problem where we determine if there exists two vertex disjoint paths of a specified parity between two pairs of terminals. Using a similar technique, we give an O(|E(G)||V(G)|α(|E(G)|,|V(G)|)) algorithm for the parity two disjoint rooted paths problem on an input graph G, where α(|E(G)|,|V(G)|) is the inverse of the Ackermann function. We note that this clearly gives an algorithm for the well-known non-parity version of the two disjoint rooted paths problem [19, 50, 52, 55, 58]. We then extend our approach to give a polynomial time algorithm which determines, for any fixed k, whether there exists a cycle of a given parity through k independent input edges. This generalizes the non-parity version of the algorithm in [22]. Thomassen [61] gave a polynomial algorithm for the case k = 2 and hoped to use this algorithm to recognize a totally odd K4-subdivision. Our algorithm runs in O(|E(G)||V(G)|α(|E(G)|,|V(G)|)) for any fixed k. Finally, we give an O(|V(G)|2 + |E(G)|α(|E(G)|,|V(G)|log|V(G)|)) algorithm to decide whether a graph contains k disjoint paths from A to B (with |A| = |B| = k) that are not all of the same parity. This answers a conjecture of Thomassen [60]. This problem arises from the study of totally odd-K4-subdivisions in 3-connected graphs [60].
-
three coloring triangle free planar graphs in linear time
Symposium on Discrete Algorithms, 2009Co-Authors: Zdeněk Dvořak, Ken-ichi Kawarabayashi, Robin ThomasAbstract:Grotzsch's theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms to find a 3-coloring, but it is not clear how to find such a coloring in linear time (Kowalik used a nontrivial data structure to construct an O(n log n) algorithm). We design a linear-time algorithm to find a 3-coloring of a given triangle-free planar graph. The algorithm avoids using any complex data structures, which makes it easy to implement. As a by-product we give a yet simpler proof of Grotzsch's theorem.
-
6 critical graphs on the klein bottle
SIAM Journal on Discrete Mathematics, 2008Co-Authors: Ken-ichi Kawarabayashi, Jan Kyncl, Daniel Kral, Bernard LidickýAbstract:We provide a complete list of 6-critical graphs that can be embedded on the Klein bottle settling a problem of Thomassen [J. Combin. Theory Ser. B, 70 (1997), pp. 67-100, Problem 3]. The list consists of nine nonisomorphic graphs which have altogether 18 nonisomorphic 2-cell embeddings and one embedding that is not 2-cell.
-
six critical graphs on the klein bottle
Electronic Notes in Discrete Mathematics, 2008Co-Authors: Nathan Chenette, Luke Postle, Noah Streib, Carl Yerger, Robin Thomas, Daniel Kral, Jan Kyncl, Ken-ichi Kawarabayashi, Bernard LidickýAbstract:Abstract We exhibit an explicit list of nine graphs such that a graph drawn in the Klein bottle is 5-colorable if and only if it has no subgraph isomorphic to a member of the list. This answers a question of Thomassen [J. Comb. Theory Ser. B 70 (1997), 67–100] and implies an earlier result of Kral', Mohar, Nakamoto, Pangrac and Suzuki that an Eulerian triangulation of the Klein bottle is 5-colorable if and only if it has no complete subgraph on six vertices.
