Search

We answer a question of Gyárfás and Sárközy from 2013 by showing that every 2-edge-coloured complete 3-uniform hypergraph can be partitioned into two monochromatic tight paths of different colours. We also give a lower bound for the number of tight paths needed to partition any 2-edge-coloured complete k-partite k-uniform hypergraph. Finally, we show that any 2-edge coloured complete bipartite graph has a partition into a monochromatic cycle and a monochromatic path, of different colours, unless the colouring is a split colouring.

We prove the Erdős–Sós conjecture for trees with bounded maximum degree and large dense host graphs. As a corollary, we obtain an upper bound on the multicolour Ramsey number of large trees whose maximum degree is bounded by a constant.

We propose the following conjecture: For every fixed $\alpha\in [0,\frac 13)$, each graph of minimum degree at least $(1+\alpha)\frac k2$ and maximum degree at least $2(1-\alpha)k$ contains each tree with $k$ edges as a subgraph. Our main result is an approximate version of the conjecture for bounded degree trees and large dense host graphs. We also show that our conjecture is asymptotically best possible. The proof of the approximate result relies on a second result, which we believe to be interesting on its own. Namely, we can embed any bounded degree tree into host graphs of minimum/maximum degree asymptotically exceeding $\frac k2$ and $\frac 43k$, respectively, as long as the host graph avoids a specific structure.

The analogue of Hadwiger's conjecture for the immersion order, a conjecture independently posed by Lescure and Meyniel, and by Abu-Khzam and Langston, states that every graph G which does not contain the complete graph Kt+1 as an immersion satisfies χ(G) ≤ t. If true, this conjecture would imply that every graph with n vertices and independence number α contains K ⌈ n α ⌉ as an immersion (and if α = 2, the two statements are known to be equivalent). The immersion conjecture has been tackled with more success than its graph minors counterpart: not only is a linear upper bound known for the chromatic number of Kt+1-immersion-free graphs, but the best bound currently known is very close to optimal. Namely, the currently best bound in this respect is due to Gauthier, Le and Wollan, who recently proved that every graph not containing Kt+1 as an immersion satisfies χ(G) ≤ 3.54t + 7. Their result implies that any graph with n vertices and independence number α contains K ⌈ n 3.54 α − c ⌉ as an immersion, where c K 2 ⌊ n 5 ⌋ as an immersion. We show that any graph with n vertices and independence number 3 contains a clique immersion on at least ⌊ 2 n 9 ⌋ − 1 vertices, and any graph with n vertices and independence number 4 contains a clique immersion on at least ⌊ 4 n 27 ⌋ − 1 vertices. Thus, comparing to the bound from above, in both cases we roughly double the size of the immersion obtained.

Diagnosis of cerebrospinal fluid (CSF) infections in patients following neurosurgical procedures can be challenging. CSF lactate (LCSF) has been shown to assist in differentiating bacterial from non-bacterial meningitis in non-neurosurgical patients. The use of lactate in diagnosing CSF-related infections following neurosurgical procedures has been described in adults. The goal of this study was to describe the role of LCSF levels in diagnosing CSF-related infections among neurosurgical children. We retrospectively collected data for all pediatric patients treated at a large tertiary pediatric neurosurgical department, for whom CSF samples were collected over a 2-year period. Lactate levels were correlated with other CSF parameters, surgical parameters, presence of CSF infection, and source of CSF sample (lumbar, ventricular, or pseudomeningocele). A total of 215 CSF samples from 162 patients were analyzed. We found a correlation between lactate levels and other CSF parameters. Lactate levels displayed an inconsistent correlation with infection depending on sample origin. Irrespective of the CSF source, lactate levels could not sufficiently discriminate between those with or without infection. Lactate levels were correlated with recent surgery, and, in some of the subgroups, to the extent of blood in CSF. LCSF levels are influenced by many factors, including the source of sample, recent surgery, and the presence of subarachnoid or ventricular blood secondary to surgery. The added value of LCSF for diagnosing CSF infections in children with a history of neurosurgical procedures is unclear and may be influenced by the extent of blood in the CSF.

It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable graph without an induced path on t vertices, computes a coloring with $$\max \left\{ 5,2\left\lceil \frac{t-1}{2}\right\rceil -2\right\} $$ many colors. If the input graph is triangle-free, we only need $$\max \left\{ 4,\left\lceil \frac{t-1}{2}\right\rceil +1\right\} $$ many colors. The running time of our algorithm is $$O((3^{t-2}+t^2)m+n)$$ if the input graph has n vertices and m edges.

We show that any complete $k$-partite graph $G$ on $n$ vertices, with $k \ge 3$, whose edges are two-coloured, can be covered with two vertex-disjoint monochromatic paths of distinct colours. We prove this under the necessary assumption that the largest partition class of $G$ contains at most $n/2$ vertices. This extends known results for complete and complete bipartite graphs. Secondly, we show that in the same situation, all but $o(n)$ vertices of the graph can be covered with two vertex-disjoint monochromatic cycles of distinct colours, if colourings close to a split colouring are excluded. From this we derive that the whole graph, if large enough, may be covered with 14 vertex-disjoint monochromatic cycles.

For any odd $t\ge 9$, we present a polynomial-time algorithm that solves the $3$-colouring problem, and finds a $3$-colouring if one exists, in $P_{t}$-free graphs of odd girth at least $t-2$. In particular, our algorithm works for $(P_9, C_3, C_5)$-free graphs, thus making progress towards determining the complexity of $3$-colouring in $P_t$-free graphs, which is open for $t\ge 8$., 21 pages

International audience; A well-known conjecture of Erdős and Sós states that every graph with average degree exceeding $m−1$ contains every tree with m edges as a subgraph. We propose a variant of this conjecture, which states that every graph of maximum degree exceeding m and minimum degree at least $[\frac{2m}{3}]$ contains every tree with m edges. As evidence for our conjecture we show (i) for every m there is a g(m) such that the weakening of the conjecture obtained by replacing the first m by g(m) holds, and (ii) there is a $\gamma > 0$ such that the weakening of the conjecture obtained by replacing $[\frac{2m} {3}$ by $(1 − \gamma)m$ holds.

We survey results and open problems relating degree conditions with tree containment in graphs, random graphs, digraphs, and hypergraphs, and their applications in Ramsey theory.

Objective In patients with drug-resistant epilepsy, reduction of seizure duration and frequency at an early age is beneficial. Vagal nerve stimulator (VNS) was shown to reduce seizure frequency and duration in children; however, data in children under the age of 12 years are sparse. The aim of this study was to compare seizure outcome and quality of life after early (≤ 5 years of age) and late (> 5 years of age) implantation of VNS in children. Methods This study reviewed 45 consecutive children undergoing VNS implantation. Primary outcome measure was the reduction of seizure frequency. Secondary outcome measures were epilepsy outcome assessed by the McHugh and Engel classifications, reduction of antiepileptic drugs (AEDs), psychomotor development, and quality of life measured by the Pediatric Quality of Life (PEDSQL™) questionnaire and caregiver impression (CGI) scale. The mean follow-up time was 72.3 months (± 39.8 months). Results Out of 45 patients included, in 14 (31.1%), VNS was implanted early and in 31, (68.9%) late. Reduction of seizure frequency, McHugh and Engel classifications, and reduction of AED were comparable in both groups. Quality of life measured by the CGI scale (2.1 ± 1.7 in the early group vs. 3.6 ± 1.6 in the late group; p = 0.004), as well as the difference of total PEDSQL™ Core scores (12.0 ± 24.0 in the early group vs. − 5.2 ± 14.9 in the late group; p = 0.01) and cognitive PEDSQL™ Core (30.6 ± 32.0 in the early group vs. 2.4 ± 24.3 in the late group; p = 0.03) between preoperative and follow-up was significantly higher in the early implantation group. Conclusion Early VNS implantation in children leads to a significantly better quality of life and cognitive outcome compared with late implantation while reduction of seizure frequency and epilepsy outcome seems comparable. Therefore, in children with drug-resistant epilepsy, VNS implantation should be considered as early as possible.

We show that for all l , k , n with l ≤ k ∕ 2 and ( k − l ) dividing n the following hypergraph-variant of Lehel’s conjecture is true. Every 2-edge-colouring of the k -uniform complete hypergraph K n ( k ) on n vertices has at most two disjoint monochromatic l -cycles in different colours that together cover all but at most 4 ( k − l ) vertices. If l ≤ k ∕ 3 , then at most two l -cycles cover all but at most 2 ( k − l ) vertices. Furthermore, we can cover all vertices with at most 4 (3 if l ≤ k ∕ 3 ) disjoint monochromatic l -cycles.

We characterize the virtually nilpotent finitely generated groups (or, equivalently by Gromov’s theorem, groups of polynomial growth) for which the Domino Problem is decidable: These are the virtually free groups, i.e. finite groups, and those having Z as a subgroup of finite index. Our proof uses a reduction of the undecidability of the domino problem on groups with infinite tree-width to the undecidability of the domino problem on Z2. This is achieved by relating infinite tree-width to the existence of a certain structure, resembling a half-grid, by an extension of a result of Halin. Since it is known that any finitely generated group of finite tree-width is virtually free, we thus obtain the desired result.

We show that any 2-colouring of the 3-uniform complete hypergraph K n ( 3 ) on n vertices contains two disjoint monochromatic tight cycles of distinct colours covering all but o(n) vertices of K n ( 3 ) . The same result holds if we replace tight cycles with loose cycles.

In this paper we present a polynomial time algorithm that determines if an input graph containing no induced seven-vertex path is 3-colorable. This affirmatively answers a question posed by Randerath, Schiermeyer and Tewes in 2002. Our algorithm also solves the list-coloring version of the 3-coloring problem, where every vertex is assigned a list of colors that is a subset of {1,2,3}, and gives an explicit coloring if one exists. Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina Fil: Chudnovsky, Mariana. University of Princeton; Estados Unidos Fil: Maceli, Peter. Canisius College; Estados Unidos Fil: Schaudt, Oliver. Universitat zu Köln; Alemania Fil: Stein, Maya. Universidad de Chile; Chile Fil: Zhong, Mingxian. Columbia University; Estados Unidos

We consider the problem of clique coloring, that is, coloring the vertices of a given graph such that no (maximal) clique of size at least two is monocolored. It is known that interval graphs are 2 -clique colorable. In this paper we prove that B 1 -EPG graphs (edge intersection graphs of paths on a grid, where each path has at most one bend) are 4 -clique colorable. Moreover, given a B 1 -EPG representation of a graph, we provide a linear time algorithm that constructs a 4 -clique coloring of it.

This is the last paper of a series of four papers in which we prove the following relaxation of the Loebl-Komlos-Sos Conjecture: For every $\alpha>0$ there exists a number~$k_0$ such that for every $k>k_0$ every $n$-vertex graph $G$ with at least $(\frac12+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first two papers of this series, we decomposed the host graph $G$, and found a suitable combinatorial structure inside the decomposition. In the third paper, we refined this structure, and proved that any graph satisfying the conditions of the above approximate version of the Loebl-Komlos-Sos Conjecture contains one of ten specific configurations. In this paper we embed the tree $T$ in each of the ten configurations., Comment: 81 pages, 12 figures. A fix reflecting the change of Preconfiguration Clubs in Paper III, additional small changes

We show that for any coloring of the edges of the complete bipartite graph $K_{n,n}$ with three colors there are five disjoint monochromatic cycles which together cover all but $o(n)$ of the vertices. In the same situation, 18 disjoint monochromatic cycles together cover all vertices.

This is the third of a series of four papers in which we prove the following relaxation of the Loebl-Komlos-Sos Conjecture: For every $\alpha>0$ there exists a number $k_0$ such that for every $k>k_0$ every $n$-vertex graph $G$ with at least $(\frac12+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first paper of the series, we gave a decomposition of the graph $G$ into several parts of different characteristics. In the second paper, we found a combinatorial structure inside the decomposition. In this paper, we will give a refinement of this structure. In the forthcoming fourth paper, the refined structure will be used for embedding the tree $T$., Comment: 59 pages, 4 figures; further comments by a referee incorporated; this includes a subtle but important fix to Lemma 5.1; as a consequence, Preconfiguration Clubs was changed

This is the second of a series of four papers in which we prove the following relaxation of the Loebl-Komlos--Sos Conjecture: For every $\alpha>0$ there exists a number $k_0$ such that for every $k>k_0$ every $n$-vertex graph $G$ with at least $(\frac12+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first paper of the series, we gave a decomposition of the graph $G$ into several parts of different characteristics; this decomposition might be viewed as an analogue of a regular partition for sparse graphs. In the present paper, we find a combinatorial structure inside this decomposition. In the last two papers, we refine the structure and use it for embedding the tree $T$., Comment: 38 pages, 4 figures; new is Section 5.1.1; accepted to SIDMA

The analogue of Hadwiger's conjecture for the immersion order states that every graph $G$ contains $K_{\chi (G)}$ as an immersion. If true, it would imply that every graph with $n$ vertices and independence number $\alpha$ contains $K_{\lceil \frac n\alpha\rceil}$ as an immersion. The best currently known bound for this conjecture is due to Gauthier, Le and Wollan, who recently proved that every graph $G$ contains an immersion of a clique on $\bigl\lceil \frac{\chi (G)-4}{3.54}\bigr\rceil$ vertices. Their result implies that every $n$-vertex graph with independence number $\alpha$ contains an immersion of a clique on $\bigl\lceil \frac{n}{3.54\alpha}-1.13\bigr\rceil$ vertices. We improve on this result for all $\alpha\ge 3$, by showing that every $n$-vertex graph with independence number $\alpha\ge 3$ contains an immersion of a clique on $\bigl\lfloor \frac {n}{2.25 \alpha - f(\alpha)} \bigr\rfloor - 1$ vertices, where $f$ is a nonnegative function., Comment: 13 pages, 1 figure. Minor changes according to referees' suggestions

The diagnosis and timely treatment of shunt infections (SI) in children is of paramount importance. In some cases, the standard cerebrospinal fluid (CSF) variables will not be sufficient for an accurate diagnosis of SI. CSF lactate (LCSF) has been found to assist in differentiating bacterial from nonbacterial meningitis in non-neurosurgical patients. To the best of our knowledge, the use of lactate in diagnosing or confirming the presence of SI has not yet been discussed. The goal of the present study was to describe the role of LCSF levels in children with shunts and Ommaya reservoirs and to evaluate its role in the accurate diagnosis of shunt-related infection.We retrospectively collected data for a consecutive series of pediatric patients treated at a large tertiary pediatric neurosurgical department, for whom CSF samples from shunts had been collected during a 2-year period (2016-2017). The lactate levels were correlated with the presence of SI.A total of 61 CSF samples were analyzed, with 6 SIs found. The LCSF levels and white blood cell count were both found to correlate with the presence of CSF infections. A cutoff value of ≥2.95 mmol/L reached a sensitivity of 83%, specificity of 83%, and positive predictive value of 50%. LCSF2.95 mmol/L had a negative predictive value of 96%.LCSF levels can be used as an additional chemical marker for the diagnosis and confirmation of SIs. An LCSF value of2.95 mmol/L had a high negative predictive value.

Guidelines on the administration of prophylactic antiepileptic drugs (AED), and specifically levetiracetam, for brain tumor surgery are still lacking. In this two-center matched cohort study, we aim to compare the proportion of postoperative seizures during follow-up after supratentorial tumor surgery in patients receiving no seizure prophylaxis, and those treated with levetiracetam perioperatively. Three hundred sixteen consecutive patients undergoing supratentorial tumor surgery, without history of seizures were included: 207 patients did not receive AED (no AED group), and 109 patients received levetiracetam perioperatively (levetiracetam group). The primary outcome measure was the rate of postoperative seizures. Additionally, uni- and multivariate analyses assessing possible risk factors for postoperative seizures were performed. No statistically significant difference for the occurrence of postoperative seizures was found between the two groups (10.1%, n = 21 in the no AED group vs. 9.2%, n = 10, in the levetiracetam group; p = 0.69, OR 0.9 [0.4–2.0), NNT 103 [12.9–17.1]). After propensity score matching, the primary outcome was observed in 13 patients (12.4%) from the no AED group and in 9 patients (8.6%) from the levetiracetam group (p = 0.50, OR 0.7 [0.3–1.6], NNT 26.3 [8.3–22.4]). Among all analyzed possible risk factors for postoperative seizures, only postoperative infarction showed a statistically significant association with higher seizure rates in multivariate analysis (OR 8.2 [1.1–60.6], p = 0.04). Prophylactic treatment with levetiracetam after brain tumor surgery showed no statistically significant effect in preventing postoperative seizures. However, in case a postoperative infarction occurs, its administration might be indicated.

In this paper and a companion paper, we prove that, if $m$ is sufficiently large, every graph on $m+1$ vertices that has a universal vertex and minimum degree at least $\lfloor \frac{2m}{3} \rfloor$ contains each tree $T$ with $m$ edges as a subgraph. Our result confirms, for large $m$, an important special case of a recent conjecture by Havet, Reed, Stein, and Wood. The present paper already contains an approximate version of the result., Comment: 59 pages

We prove that, if $m$ is sufficiently large, every graph on $m+1$ vertices that has a universal vertex and minimum degree at least $\lfloor \frac{2m}{3} \rfloor$ contains each tree $T$ with $m$ edges as a subgraph. Our result confirms, for large $m$, an important special case of a conjecture by Havet, Reed, Stein, and Wood. The present paper builds on the results of a companion paper in which we proved the statement for all trees having a vertex that is adjacent to many leaves., Comment: 31 pages

We conjecture that every $n$-vertex graph of minimum degree at least $\frac k2$ and maximum degree at least $2k$ contains all trees with $k$ edges as subgraphs. We prove an approximate version of this conjecture for trees of bounded degree and dense host graphs. Our work also has implications on the Erd\H os--S\'os conjecture and the $\frac 23$-conjecture. We prove an approximate version of both conjectures for bounded degree trees and dense host graphs., Comment: 54 pages

We show that any colouring with three colours of the edges of the complete bipartite graph K n , n contains 18 vertex-disjoint monochromatic cycles which together cover all vertices. The minimum number of cycles needed for such a covering is five, and we show that this lower bound is asymptotically true. This extends known results for complete graphs.

An edge coloring of a graph is said to be an r-local coloring if the edges incident to any vertex are colored with at most r colors. Generalizing a result of Bessy and Thomasse, we prove that the vertex set of any 2-locally colored complete graph may be partitioned into two disjoint monochromatic cycles of different colors. Moreover, for any natural number r, we show that the vertex set of any r-locally colored complete graph may be partitioned into Or2logr disjoint monochromatic cycles. This generalizes a result of Erdi¾?s, Gyarfas, and Pyber.

We prove that the list chromatic index of a graph of maximum degree Δ and treewidth i¾?2Δ-3 is Δ; and that the total chromatic number of a graph of maximum degree Δ and treewidth i¾?Δ/3+1 is Δ+1. This improves results by Meeks and Scott.

It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on t vertices, for fixed t. We propose an algorithm that, given a 3-colorable graph without an induced path on t vertices, computes a coloring with \(\max \left\{ 5,2\left\lceil \frac{t-1}{2}\right\rceil -2\right\} \) many colors. If the input graph is triangle-free, we only need \(\max \left\{ 4,\left\lceil \frac{t-1}{2}\right\rceil +1\right\} \) many colors. The running time of our algorithm is \(O((3^{t-2}+t^2)m+n)\) if the input graph has n vertices and m edges.

Bricks are 3-connected bicritical graphs. Together with braces, they arise in matching theory as building blocks for matching covered graphs. We prove that every minimal brick on n vertices has at least n 9 vertices of degree at most 4. This proves a relaxed version of a conjecture of Norine and Thomas, which suggests that every minimal brick has some fixed positive fraction of vertices of degree 3.

Advancing the sparse regularity method, we prove one-sided and two-sided regularity inheritance lemmas for subgraphs of bijumbled graphs, improving on results of Conlon, Fox and Zhao [Adv. Math. 256 (2014), 206--290]. These inheritance lemmas also imply improved $H$-counting lemmas for subgraphs of bijumbled graphs, for some $H$., Comment: 28 pages, no figures

The determination of the stability of the long-lived consensus problem is a fundamental open problem in distributed systems. We concentrate on the memoryless binary case with geodesic paths. We offer a conjecture on the stability in this case, exhibit two classes of colourings which attain this conjectured bound, and improve the known lower bounds for all colourings. We also introduce a related parameter, which measures the stability only for certain geodesics, and for which we also prove lower bounds.

A graph is called t-perfect, if its stable set polytope is defined by non-negativity, edge and odd-cycle inequalities. We characterise the class of all claw-free t-perfect graphs by forbidden t-minors, and show that they are 3-colourable. Moreover, we determine the chromatic number of claw-free h-perfect graphs and give a polynomial-time algorithm to compute an optimal colouring.

Bounds on the minimum degree and on the number of vertices at- taining it have been much studied for finite edge-/vertex-minimally k- connected/k-edge-connected graphs. We give an overview of the results known for finite graphs, and show that most of these carry over to infinite graphs if we consider ends of small degree as well as vertices., Comment: 15 pages

We investigate the end spaces of infinite dual graphs. We show that there exists a natural homeomorphism * between the end spaces of a graph and its dual, and that * preserves the ‘end degree’. In particular, * maps thick ends to thick ends. Along the way, we prove that Tutte-connectivity is invariant under taking (infinite) duals.

We characterise the class of all claw-free t-perfect graphs by forbidden t-minors. Moreover, we show that claw-free t-perfect graphs are 3-colourable. Such a colouring can be obtained in polynomial time.

The Loebl–Komlos–Sos conjecture states that, given a graph G and a natural number k , if at least half the vertices of G have degree at least k , then any tree with at most k edges is a subgraph of G . We prove an approximate version of this conjecture for large graphs and k linear in | V ( G ) | .

We introduce a natural extension of the vertex degree to ends. For the cycle space C(G) as proposed by Diestel and Kuhn [4, 5], which allows for infinite cycles, we prove that the edge set of a locally finite graph G lies in C(G) if and only if every vertex and every end has even degree. In the same way we generalise to locally finite graphs the characterisation of the cycles in a finite graph as its 2-regular connected subgraphs.

We consider a generalisation of the classical Ramsey theory setting to a setting where each of the edges of the underlying host graph is coloured with a {\em set} of colours (instead of just one colour). We give bounds for monochromatic tree covers in this setting, both for an underlying complete graph, and an underlying complete bipartite graph. We also discuss a generalisation of Ramsey numbers to our setting and propose some other new directions. Our results for tree covers in complete graphs imply that a stronger version of Ryser's conjecture holds for $k$-intersecting $r$-partite $r$-uniform hypergraphs: they have a transversal of size at most $r-k$. (Similar results have been obtained by Kir\'aly et al., see below.) However, we also show that the bound $r-k$ is not best possible in general., Comment: 23 pages

The determination of the (in-)stability of the long-lived consensus problem is a fundamental open problem in distributed systems. We concentrate on the memoryless binary case with geodesic paths. For this case, we offer a conjecture on the instability, measured by the parameter inst, exhibit two classes of colourings which attain the conjectured bound, and improve the known lower bounds for all colourings. We also introduce a related parameter, winst, which measures the stability only for certain geodesics, and for which we also prove lower bounds.

A set of vertices X of a graph G is convex if no shortest path between two vertices in X contains a vertex outside X. We prove that for fixed p ? 1 , all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time.