Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSome Results on $k$-Tur{a}n-good Graphs
225
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For a graph $H$ and a $k$-chromatic graph $F,$ if the Turan graph $T_{k-1}(n)$ has the maximum number of copies of $H$ among all $n$-vertex $F$-free graphs (for $n$ large enough), then $H$ is called $F$-Turan-good, or $k$-Turan-good for short if $F$ is $K_k.$ In this paper, we construct some new classes of $k$-Turan-good graphs and prove that $P_4$ and $P_5$ are $k$-Turan-good for $kge4.$
rate research
Read More
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 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.
Given a graph $H$ and a positive integer $n,$ the Tur{a}n number of $H$ for the order $n,$ denoted ${rm ex}(n,H),$ is the maximum size of a simple graph of order $n$ not containing $H$ as a subgraph. The book with $p$ pages, denoted $B_p$, is the graph that consists of $p$ triangles sharing a common edge. Bollob{a}s and ErdH{o}s initiated the research on the Tur{a}n number of book graphs in 1975. The two numbers ${rm ex}(p+2,B_p)$ and ${rm ex}(p+3,B_p)$ have been determined by Qiao and Zhan. In this paper we determine the numbers ${rm ex}(p+4,B_p),$ ${rm ex}(p+5,B_p)$ and ${rm ex}(p+6,B_p),$ and characterize the corresponding extremal graphs for the numbers ${rm ex}(n,B_p)$ with $n=p+2,,p+3,,p+4,,p+5.$
Given a proper edge coloring $varphi$ of a graph $G$, we define the palette $S_{G}(v,varphi)$ of a vertex $v in V(G)$ as the set of all colors appearing on edges incident with $v$. The palette index $check s(G)$ of $G$ is the minimum number of distinct palettes occurring in a proper edge coloring of $G$. In this paper we give various upper and lower bounds on the palette index of $G$ in terms of the vertex degrees of $G$, particularly for the case when $G$ is a bipartite graph with small vertex degrees. Some of our results concern $(a,b)$-biregular graphs; that is, bipartite graphs where all vertices in one part have degree $a$ and all vertices in the other part have degree $b$. We conjecture that if $G$ is $(a,b)$-biregular, then $check{s}(G)leq 1+max{a,b}$, and we prove that this conjecture holds for several families of $(a,b)$-biregular graphs. Additionally, we characterize the graphs whose palette index equals the number of vertices.
A proper edge coloring of a graph $G$ with colors $1,2,dots,t$ is called a emph{cyclic interval $t$-coloring} if for each vertex $v$ of $G$ the edges incident to $v$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$. We prove that a bipartite graph $G$ with even maximum degree $Delta(G)geq 4$ admits a cyclic interval $Delta(G)$-coloring if for every vertex $v$ the degree $d_G(v)$ satisfies either $d_G(v)geq Delta(G)-2$ or $d_G(v)leq 2$. We also prove that every Eulerian bipartite graph $G$ with maximum degree at most $8$ has a cyclic interval coloring. Some results are obtained for $(a,b)$-biregular graphs, that is, bipartite graphs with the vertices in one part all having degree $a$ and the vertices in the other part all having degree $b$; it has been conjectured that all these have cyclic interval colorings. We show that all $(4,7)$-biregular graphs as well as all $(2r-2,2r)$-biregular ($rgeq 2$) graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this settles in the affirmative, a conjecture of Petrosyan and Mkhitaryan.
We consider finite simple graphs. Given a graph $H$ and a positive integer $n,$ the Tur{a}n number of $H$ for the order $n,$ denoted ${rm ex}(n,H),$ is the maximum size of a graph of order $n$ not containing $H$ as a subgraph. ErdH{o}s posed the following problem in 1990: For which graphs $H$ is it true that every graph on $n$ vertices and ${rm ex}(n,H)+1$ edges contains at least two $H$s? Perhaps this is always true. We solve the second part of this problem in the negative by proving that for every integer $kge 4,$ there exists a graph $H$ of order $k$ and at least two orders $n$ such that there exists a graph of order $n$ and size ${rm ex}(n,H)+1$ which contains exactly one copy of $H.$ Denote by $C_4$ the $4$-cycle. We also prove that for every integer $n$ with $6le nle 11,$ there exists a graph of order $n$ and size ${rm ex}(n,C_4)+1$ which contains exactly one copy of $C_4,$ but for $n=12$ or $n=13,$ the minimum number of copies of $C_4$ in a graph of order $n$ and size ${rm ex}(n,C_4)+1$ is $2.$
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
