اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديد$k$-Critical Graphs in $P_5$-Free Graphs
152
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 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 theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is $(k-1)$-colorable. In this paper, we initiate a systematic study of the finiteness of $k$-vertex-critical graphs in subclasses of $P_5$-free graphs. Our main result is a complete classification of the finiteness of $k$-vertex-critical graphs in the class of $(P_5,H)$-free graphs for all graphs $H$ on 4 vertices. To obtain the complete dichotomy, we prove the finiteness for four new graphs $H$ using various techniques -- such as Ramsey-type arguments and the dual of Dilworths Theorem -- that may be of independent interest.
قيم البحث
اقرأ أيضاً
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
y because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is $(k-1)$-colorable. In this paper, we prove that for every fixed integer $kge 1$, there are only finitely many $k$-vertex-critical ($P_5$,gem)-free graphs and $(P_5,overline{P_3+P_2})$-free graphs. To prove the results we use a known structure theorem for ($P_5$,gem)-free graphs combined with properties of $k$-vertex-critical graphs. Moreover, we characterize all $k$-vertex-critical ($P_5$,gem)-free graphs and $(P_5,overline{P_3+P_2})$-free graphs for $k in {4,5}$ using a computer generation algorithm.
The Borodin-Kostochka Conjecture states that for a graph $G$, if $Delta(G) geq 9$ and $omega(G) leq Delta(G)-1$, then $chi(G)leqDelta(G) -1$. We prove the Borodin-Kostochka Conjecture for $(P_5, text{gem})$-free graphs, i.e., graphs with no induced $P_5$ and no induced $K_1vee P_4$.
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 characteri
zed 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.
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
ta_U$ and $Delta_V$ denote the maximum degree in $U$ and $V$, respectively, is lexicographically minimum over all such graphs. $G$ is $k$-critical bipartite if deleting at most $k=n-m$ vertices from $U$ creates $G$ that has a complete matching, i.e., a matching of size $m$. We show that, if $m(n-m+1)/n$ is an integer, then a solution of the M$k$CBG-$(n,m)$ problem can be found among $(a,b)$-regular bipartite graphs of order $(n,m)$, with $a=m(n-m+1)/n$, and $b=n-m+1$. If $a=m-1$, then all $(a,b)$-regular bipartite graphs of order $(n,m)$ are $k$-critical bipartite. For $a<m-1$, it is not the case. We characterize the values of $n$, $m$, $a$, and $b$ that admit an $(a,b)$-regular bipartite graph of order $(n,m)$, with $b=n-m+1$, and give a simple construction that creates such a $k$-critical bipartite graph whenever possible. Our techniques are based on Halls marriage theorem, elementary number theory, linear Diophantine equations, properties of integer functions and congruences, and equations involving them.
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
a$-critical if it is connected, class 2 and $chi(G-e)<chi(G)$ for every $ein E(G)$. A long-standing conjecture of Vizing from 1968 states that every $Delta$-critical graph on $n$ vertices has at least $(n(Delta-1)+ 3)/2$ edges. We initiate the study of determining the minimum number of edges of class 1 graphs $G$, in addition, $chi(G+e)=chi(G)+1$ for every $ein E(overline{G})$. Such graphs have intimate relation to $(P_3; k)$-co-critical graphs, where a non-complete graph $G$ is $(P_3; k)$-co-critical if there exists a $k$-coloring of $E(G)$ such that $G$ does not contain a monochromatic copy of $P_3$ but every $k$-coloring of $E(G+e)$ contains a monochromatic copy of $P_3$ for every $ein E(overline{G})$. We use the bound on the size of the aforementioned class 1 graphs to study the minimum number of edges over all $(P_3; k)$-co-critical graphs. We prove that if $G$ is a $(P_3; k)$-co-critical graph on $nge k+2$ vertices, then [e(G)ge {k over 2}left(n- leftlceil {k over 2} rightrceil - varepsilonright) + {lceil k/2 rceil+varepsilon choose 2},] where $varepsilon$ is the remainder of $n-lceil k/2 rceil $ when divided by $2$. This bound is best possible for all $k ge 1$ and $n ge leftlceil {3k /2} rightrceil +2$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
