Institutions | LORIA (Nancy, France), Radboud University (Nijmegen, Netherlands), ICube (Strasbourg, France) | |||||
---|---|---|---|---|---|---|
Status | Phd Student under the direction of Ross J. Kang and Jean-Sébastien Sereni | |||||
Location | Laboratoire ICube, équipe CSTB, bureau 551, 11 rue Humann, 67000 Strasbourg, France | |||||
Links | CV | ResearchGate | ORCID | dblp | Scholar | arXiv |
Interests | Graph Theory, Combinatorics, Probabilistic Methods |
Publications and Submissions |
Workshops, Conferences, Seminars |
Teaching |
Others |
Given a graph $G$, the strong clique number $\omega_2'(G)$ of $G$ is the cardinality of a largest collection of edges every pair of which are incident or connected by an edge in $G$. We study the strong clique number of graphs missing some set of cycle lengths. For a graph $G$ of large enough maximum degree $\Delta$, we show among other results the following: $\omega_2'(G)\le5\Delta^2/4$ if $G$ is triangle-free; $\omega_2'(G)\le3(\Delta-1)$ if $G$ is $C_4$-free; $\omega_2'(G)\le\Delta^2$ if $G$ is $C_{2k+1}$-free for some $k\ge 2$. These bounds are attained by natural extremal examples. Our work extends and improves upon previous work of Faudree, Gyárfás, Schelp and Tuza (1990), Mahdian (2000) and Faron and Postle (2019). We are motivated by the corresponding problems for the strong chromatic index. |
The Petersen colouring conjecture states that every bridgeless cubic graph admits an edge-colouring with $5$ colours such that for every edge $e$, the set of colours assigned to the edges adjacent to $e$ has cardinality either $2$ or $4$, but not $3$. We prove that every bridgeless cubic graph $G$ admits an edge-colouring with $4$ colours such that at most $\frac45\cdot|V(G)|$ edges do not satisfy the above condition. This bound is tight and the Petersen graph is the only connected graph for which the bound cannot be decreased. We obtain such a $4$-edge-colouring by using a carefully chosen subset of edges of a perfect matching, and the analysis relies on a simple discharging procedure with essentially no reductions and very few rules. |
Given $\varepsilon>0$, there exists $f_0$ such that, if $f_0 \le f \le Δ^2+1$, then for any graph $G$ on $n$ vertices of maximum degree $Δ$ in which the neighbourhood of every vertex in $G$ spans at most $Δ^2/f$ edges, (i) an independent set of $G$ drawn uniformly at random has at least $(1/2-\varepsilon)(n/Δ)\log f$ vertices in expectation, and (ii) the fractional chromatic number of $G$ is at most $(2+\varepsilon)Δ/\log f$. These bounds cannot in general be improved by more than a factor $2$ asymptotically. One may view these as stronger versions of results of Ajtai, Komlós and Szemerédi (1981) and Shearer (1983). The proofs use a tight analysis of the hard-core model. |
We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow-up work of Bernshteyn) on the (list) chromatic number of triangle-free graphs. In both our results, we permit the amount of colour made available to vertices of lower degree to be accordingly lower. One result concerns list colouring and correspondence colouring, while the other concerns fractional colouring. Our proof of the second illustrates the use of the hard-core model to prove a Johansson-type result, which may be of independent interest. |
We show that the strong chromatic index of unit disk graphs is efficiently $6$-approximable. This improves on $8$-approximability as shown by Barrett, Istrate, Kumar, Marathe, Thite, and Thulasidasan (2006). We also show that strong edge-$6$-colourability is NP-complete for the class of unit disk graphs. Thus there is no polynomial-time $(7/6 − \varepsilon)$-approximation unless P=NP. |
By an extensive statistical analysis in genes of bacteria, archaea, eukaryotes, plasmids and viruses, a maximal $C^3$-self-complementary trinucleotide circular code has been found to have the highest average occurrence in the reading frame of the ribosome during translation. Moreover, dinucleotide circular codes have been observed in non-coding regions of eukaryotic genomes. By using a graph-theoretical approach of circular codes recently developed, we study mixed circular codes $X \subseteq \mathcal{B}_2 \cup \mathcal{B}_3 \cup \mathcal{B}_4$, which are the union of a dinucleotide circular code $X_2 \subseteq \mathcal{B}_2$, a trinucleotide circular code $X_3 \subseteq \mathcal{B}_3$ and a tetranucleotide circular code $X_4 \subseteq \mathcal{B}_4$ where $\mathcal{B} = \{A, C, G, T\}$ is the $4$-letter genetic alphabet. Maximal mixed circular codes $X$ of (di,tri)- nucleotides, (tri,tetra)-nucleotides and (di,tri,tetra)-nucleotides are constructed, respectively. In particular, we show that any maximal dinucleotide circular code $D \subseteq \mathcal{B}_2$ of size $6$ can be embedded into a maximal mixed circular code $X \subseteq \mathcal{B}_2 \cup \mathcal{B}_3$ such that $X \cap \mathcal{B}_3$ is a maximal $C^3$-comma-free code. The growth function of self-complementary mixed circular codes of dinucleotides and trinucleotides is given. Self-complementary mixed circular codes could have been involved in primitive genetic processes and an evolutionary model based on mixed circular codes is also proposed. |
Any triangle-free graph on $n$ vertices with minimum degree at least $d$ contains a bipartite induced subgraph of minimum degree at least $d^2/(2n)$. This is sharp up to a logarithmic factor in $n$. We also provide a related extremal result for the fractional chromatic number. |
We consider distance colourings in graphs of maximum degree at most $d$ and how excluding one fixed cycle of length $\ell$ affects the number of colours required as $d \to \infty$. For vertex-colouring and $t \geqslant 1$, if any two distinct vertices connected by a path of at most $t$ edges are required to be coloured differently, then a reduction by a logarithmic (in $d$) factor against the trivial bound $O(d^t)$ can be obtained by excluding an odd cycle length $\ell \geqslant 3t$ if $t$ is odd or by excluding an even cycle length $\ell \geqslant 2t+2$. For edge-colouring and $t\geqslant 2$, if any two distinct edges connected by a path of fewer than $t$ edges are required to be coloured differently, then excluding an even cycle length $\ell \geqslant 2t$ is sufficient for a logarithmic factor reduction. For $t\geqslant 2$, neither of the above statements are possible for other parity combinations of $\ell$ and $t$. These results can be considered extensions of results due to Johansson (1996) and Mahdian (2000), and are related to open problems of Alon and Mohar (2002) and Kaiser and Kang (2014). |
Alon and Mohar (2002) posed the following problem: among all graphs $G$ of maximum degree at most $d$ and girth at least $g$, what is the largest possible value of $\chi(G^t)$, the chromatic number of the $t$-th power of $G$? For $t\geqslant 3$, we provide several upper and lower bounds concerning this problem, all of which are sharp up to a constant factor as $d\to \infty$. The upper bounds rely in part on the probabilistic method, while the lower bounds are various direct constructions whose building blocks are incidence structures. |