In this work, we introduce $t$-colorable $k$-plane drawings, that is, drawings of graphs with a $t$-edge-coloring where every edge is crossed by at most $k$ edges of each color. We give tight upper bounds on the edge- and crossing density for small values of $t$ and $k$ and show that the recognition of such drawings is NP-complete if $t\geq 2$ and $k\geq1$.
Let $G$ be the line graph of a finite simple graph, with $n\geq1$ vertices and maximum degree $\Delta$. We prove that single-site Glauber dynamics for uniform proper $q$-colorings mixes in $O_\Delta(n\log(n/\varepsilon))$ steps for every integer $q\geq\Delta+5$. Our proof uses the Bochner framework of Chen and Liu (202...
We prove that each $2$-edge-coloured spanning subgraph $G$ of $K_{n,n}$ with $\delta(G)\ge \lfloor (2n+1)/3 \rfloor$ can be covered by at most three monochromatic components. We provide a $2$-edge-coloured spanning subgraph of $K_{n,n}$ showing this minimum degree condition is sharp.
César Bispo, George Kontogeorgiou, M. Lage et al.· 0 citations
Delcourt and Postle proved that every $K_t$-minor-free graph is $O(t\log\log t)$-colorable and reduced the Linear Hadwiger Conjecture to coloring $K_t$-minor-free graphs on $O(t\log^4 t)$ vertices. In this paper, we use the star contraction technique to improve their bound for small graphs and use their reduction to ex...
The first open case of Hadwiger's conjecture states that every $K_7$-minor-free graph is 6-colorable. We prove that this is the case for $K_7^=$-minor-free graphs, where $K_7^=$ denotes the graph obtained from $K_7$ by deleting two independent edges. The proof is based on an independently interesting density result: Ev...
For fixed integers $k\ge3$ and $1\le d\le k-1$ and sufficiently large $n\in k\mathbb N$, we establish the sharp minimum $d$-degree thresholds that forces perfect matching in every $n$-vertex $k$-uniform hypergraphs. This was conjectued by Treglown and Zhao, and the $d=1$ case was conjectued by K\"uhn, Osthus and Treglo...
Jie Han, Hong-Liang Lu, Bin Wang et al.· 2 citations
We prove that every $(2K_2,K_4)$-free graph is recolorable. Equivalently, for every such graph $G$ and every $\ell\geq \chi(G)+1$, the reconfiguration graph of proper $\ell$-colorings of $G$, in which two colorings are adjacent if they differ on exactly one vertex, is connected. This resolves the final remaining open c...
Henry Echeverría, Owen Henderschedt· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
