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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given graphs $H_1, H_2$, a {red, blue}-coloring of the edges of a graph $G$is a critical coloring if $G$ has neither a red $H_1$ nor a blue $ H_2$. Anon-complete graph $G$ is $(H_1, H_2)$-co-critical if $G$ admits a criticalcoloring, but $G+e$ has no critical coloring for every edge $e$ in thecomplement of $G$. Motivated by a conjecture of Hanson and Toft from 1987, westudy the minimum number of edges over all $(C_4, K_{1,k})$-co-critical graphson $n$ vertices. We show that for all $k \ge 2 $ and $ n \ge k +\lfloor \sqrt{k-1} \rfloor +2$, if $G$ is a $(C_4,K_{1,k})$-co-critical graph on $n$vertices, then \[e(G) \ge \frac{(k+2)n}2-3- \frac{(k-1)(k+ \lfloor \sqrt{k-2}\rfloor)}2.\] Moreover, this linear bound is asymptotically best possiblefor all $k\ge3$ and $n\ge3k+4$. It is worth noting that our constructions forthe case when $ k$ is even have at least three different critical colorings.For $k=2$, we obtain the sharp bound for the minimum number of edges of $(C_4,K_{1,2})$-co-critical graphs on $n\ge5 $ vertices by showing that all suchgraphs have at least $2n-3$ edges. Our proofs rely on the structural propertiesof $(C_4,K_{1,k})$-co-critical graphs and a result of Ollmann on the minimumnumber of edges of $C_4$-saturated graphs.

Minimizing the number of edges in $(C_4, K_{1,k})$-co-critical graphs