Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn a recolouring version of Hadwigers conjecture
153
0
0.0
(
0
)
Added by
Cl\\'ement Legrand-Duchesne
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We prove that for any $varepsilon>0$, for any large enough $t$, there is a graph $G$ that admits no $K_t$-minor but admits a $(frac32-varepsilon)t$-colouring that is frozen with respect to Kempe changes, i.e. any two colour classes induce a connected component. This disproves three conjectures of Las Vergnas and Meyniel from 1981.
rate research
Read More
Hadwiger conjectured in 1943 that for every integer $t ge 1$, every graph with no $K_t$ minor is $(t-1)$-colorable. Kostochka, and independently Thomason, proved every graph with no $K_t$ minor is $O(t(log t)^{1/2})$-colorable. Recently, Postle improved it to $O(t (log log t)^6)$-colorable. In this paper, we show that every graph with no $K_t$ minor is $O(t (log log t)^{5})$-colorable.
Hadwigers conjecture is one of the most important and long-standing conjectures in graph theory. Reed and Seymour showed in 2004 that Hadwigers conjecture is true for line graphs. We investigate this conjecture on the closely related class of total graphs. The total graph of $G$, denoted by $T(G)$, is defined on the vertex set $V(G)sqcup E(G)$ with $c_1,c_2in V(G)sqcup E(G)$ adjacent whenever $c_1$ and $c_2$ are adjacent to or incident on each other in $G$. We first show that there exists a constant $C$ such that, if the connectivity of $G$ is at least $C$, then Hadwigers conjecture is true for $T(G)$. The total chromatic number $chi(G)$ of a graph $G$ is defined to be equal to the chromatic number of its total graph. That is, $chi(G)=chi(T(G))$. Another well-known conjecture in graph theory, the total coloring conjecture or TCC, states that for every graph $G$, $chi(G)leqDelta(G)+2$, where $Delta(G)$ is the maximum degree of $G$. We show that if a weaker version of the total coloring conjecture (weak TCC) namely, $chi(G)leqDelta(G)+3$, is true for a class of graphs $mathcal{F}$ that is closed under the operation of taking subgraphs, then Hadwigers conjecture is true for the class of total graphs of graphs in $mathcal{F}$. This motivated us to look for classes of graphs that satisfy weak TCC. It may be noted that a complete proof of TCC for even 4-colorable graphs (in fact even for planar graphs) has remained elusive even after decades of effort; but weak TCC can be proved easily for 4-colorable graphs. We noticed that in spite of the interest in studying $chi(G)$ in terms of $chi(G)$ right from the initial days, weak TCC is not proven to be true for $k$-colorable graphs even for $k=5$. In the second half of the paper, we make a contribution to the literature on total coloring by proving that $chi(G)leqDelta(G)+3$ for every 5-colorable graph $G$.
Motivated by a hat guessing problem proposed by Iwasawa cite{Iwasawa10}, Butler and Graham cite{Butler11} made the following conjecture on the existence of certain way of marking the {em coordinate lines} in $[k]^n$: there exists a way to mark one point on each {em coordinate line} in $[k]^n$, so that every point in $[k]^n$ is marked exactly $a$ or $b$ times as long as the parameters $(a,b,n,k)$ satisfies that there are non-negative integers $s$ and $t$ such that $s+t = k^n$ and $as+bt = nk^{n-1}$. In this paper we prove this conjecture for any prime number $k$. Moreover, we prove the conjecture for the case when $a=0$ for general $k$.
We prove a conjecture of Ohba which says that every graph $G$ on at most $2chi(G)+1$ vertices satisfies $chi_ell(G)=chi(G)$.
We consider three graphs, $G_{7,3}$, $G_{7,4}$, and $G_{7,6}$, related to Kellers conjecture in dimension 7. The conjecture is false for this dimension if and only if at least one of the graphs contains a clique of size $2^7 = 128$. We present an automated method to solve this conjecture by encoding the existence of such a clique as a propositional formula. We apply satisfiability solving combined with symmetry-breaking techniques to determine that no such clique exists. This result implies that every unit cube tiling of $mathbb{R}^7$ contains a facesharing pair of cubes. Since a faceshare-free unit cube tiling of $mathbb{R}^8$ exists (which we also verify), this completely resolves Kellers conjecture.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
