English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Strengthening Hadwiger's conjecture, Gerards and Seymour conjectured in 1995that every graph with no odd $K_t$-minor is properly $(t-1)$-colorable, this isknown as the Odd Hadwiger's conjecture. We prove a relaxation of the aboveconjecture, namely we show that every graph with no odd $K_t$-minor admits avertex $(2t-2)$-coloring such that all monochromatic components have size atmost $\lceil \frac{1}{2}(t-2) \rceil$. The bound on the number of colors isoptimal up to a factor of $2$, improves previous bounds for the same problem byKawarabayashi (2008), Kang and Oum (2019), Liu and Wood (2021), and strengthensa result by van den Heuvel and Wood (2018), who showed that the aboveconclusion holds under the more restrictive assumption that the graph is$K_t$-minor free. In addition, the bound on the component-size in our result ismuch smaller than those of previous results, in which the dependency on $t$ wasnon-explicit. Our short proof combines the method by van den Heuvel and Woodfor $K_t$-minor free graphs with some additional ideas, which make theextension to odd $K_t$-minor free graphs possible.

Improved bound for improper colorings of graphs with no odd clique minor