ﻻ يوجد ملخص باللغة العربية
Recently, Kostochka and Yancey proved that a conjecture of Ore is asymptotically true by showing that every $k$-critical graph satisfies $|E(G)|geqleftlceilleft(frac{k}{2}-frac{1}{k-1}right)|V(G)|-frac{k(k-3)}{2(k-1)}rightrceil.$ They also characterized the class of graphs that attain this bound and showed that it is equivalent to the set of $k$-Ore graphs. We show that for any $kgeq33$ there exists an $varepsilon>0$ so that if $G$ is a $k$-critical graph, then $|E(G)|geqleft(frac{k}{2}-frac{1}{k-1}+varepsilon_kright)|V(G)|-frac{k(k-3)}{2(k-1)}-(k-1)varepsilon T(G)$, where $T(G)$ is a measure of the number of disjoint $K_{k-1}$ and $K_{k-2}$ subgraphs in $G$. This also proves for $kgeq33$ the following conjecture of Postle regarding the asymptotic density: For every $kgeq4$ there exists an $varepsilon_k>0$ such that if $G$ is a $k$-critical $K_{k-2}$-free graph, then $|E(G)|geq left(frac{k}{2}-frac{1}{k-1}+varepsilon_kright)|V(G)|-frac{k(k-3)}{2(k-1)}$. As a corollary, our result shows that the number of disjoint $K_{k-2}$ subgraphs in a $k$-Ore graph scales linearly with the number of vertices and, further, that the same is true for graphs whose number of edges is close to Kostochka and Yanceys bound.
Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ or $H_2$. Let $P_t$ be the path on $t$ vertices. A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every pro
We study the problem of Minimum $k$-Critical Bipartite Graph of order $(n,m)$ - M$k$CBG-$(n,m)$: to find a bipartite $G=(U,V;E)$, with $|U|=n$, $|V|=m$, and $n>m>1$, which is $k$-critical bipartite, and the tuple $(|E|, Delta_U, Delta_V)$, where $Del
Kostochka and Yancey proved that every $4$-critical graph $G$ has $e(G) geq frac{5v(G) - 2}{3}$, and that equality holds if and only if $G$ is $4$-Ore. We show that a question of Postle and Smith-Roberge implies that every $4$-critical graph with no
A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every proper induced subgraph of $G$ has chromatic number less than $k$. The study of $k$-vertex-critical graphs for graph classes is an important topic in algorithmic graph theor
A well-known theorem of Vizing states that if $G$ is a simple graph with maximum degree $Delta$, then the chromatic index $chi(G)$ of $G$ is $Delta$ or $Delta+1$. A graph $G$ is class 1 if $chi(G)=Delta$, and class 2 if $chi(G)=Delta+1$; $G$ is $Delt