Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the size of special class 1 graphs and $(P_3; k)$-co-critical graphs
138
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 $Delta$-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$.
rate research
Read More
Given graphs $G, H_1, H_2$, we write $G rightarrow ({H}_1, H_2)$ if every ${$red, blue$}$-coloring of the edges of $G$ contains a red copy of $H_1$ or a blue copy of $H_2$. A non-complete graph $G$ is $(H_1, H_2)$-co-critical if $G rightarrow ({H}_1, H_2)$, but $G+erightarrow ({H}_1, H_2)$ for every edge $e$ in $overline{G}$. Motivated by a conjecture of Hanson and Toft from 1987, we study the minimum number of edges over all $(K_t, K_{1,k})$-co-critical graphs on $n$ vertices. We prove that for all $tge3$ and $kge 3$, there exists a constant $ell(t, k)$ such that, for all $n ge (t-1)k+1$, if $G$ is a $(K_t, K_{1,k})$-co-critical graph on $n$ vertices, then $$ e(G)ge left(2t-4+frac{k-1}{2}right)n-ell(t, k).$$ Furthermore, this linear bound is asymptotically best possible when $tin{3, 4,5}$ and all $kge3$ and $nge (2t-2)k+1$. It seems non-trivial to construct extremal $(K_t, K_{1,k})$-co-critical graphs for $tge6$. We also obtain the sharp bound for the size of $(K_3, K_{1,3})$-co-critical graphs on $nge13$ vertices by showing that all such graphs have at least $3n-4$ edges.
Given an integer $rge1$ and graphs $G, H_1, ldots, H_r$, we write $G rightarrow ({H}_1, ldots, {H}_r)$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$ for some $iin{1, ldots, r}$. A non-complete graph $G$ is $(H_1, ldots, H_r)$-co-critical if $G rightarrow ({H}_1, ldots, {H}_r)$, but $G+erightarrow ({H}_1, ldots, {H}_r)$ for every edge $e$ in $overline{G}$. In this paper, motivated by Hanson and Tofts conjecture [Edge-colored saturated graphs, J Graph Theory 11(1987), 191--196], we study the minimum number of edges over all $(K_t, mathcal{T}_k)$-co-critical graphs on $n$ vertices, where $mathcal{T}_k$ denotes the family of all trees on $k$ vertices. Following Day [Saturated graphs of prescribed minimum degree, Combin. Probab. Comput. 26 (2017), 201--207], we apply graph bootstrap percolation on a not necessarily $K_t$-saturated graph to prove that for all $tge4 $ and $kge max{6, t}$, there exists a constant $c(t, k)$ such that, for all $n ge (t-1)(k-1)+1$, if $G$ is a $(K_t, mathcal{T}_k)$-co-critical graph on $n$ vertices, then $$ e(G)ge left(frac{4t-9}{2}+frac{1}{2}leftlceil frac{k}{2} rightrceilright)n-c(t, k).$$ Furthermore, this linear bound is asymptotically best possible when $tin{4,5}$ and $kge6$. The method we develop in this paper may shed some light on attacking Hanson and Tofts conjecture.
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.
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 $Delta_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.
Let $G=(V,E)$ be a $tau$-critical graph with $tau(G)=t$. ErdH{o}s and Gallai proved that $|V|leq 2t$ and the bound $|E|leq {t+1choose 2}$ was obtained by ErdH{o}s, Hajnal and Moon. We give here the sharp combined bound $|E|+|V|leq {t+2choose 2}$ and find all graphs with equality.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
