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 |
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. |