广义图K(n,m)的全色数

1965年,M.Behzad和Vizing分别提出了著名的全着色猜想:即对于简单图G有:XT(G)≤△+2,其中△是图G的最大度.本文确定了完全图Kn的广义图K(n,m)的全色数,并利用它证明了Lm×Kn(m≥3)是第Ⅰ型的.     

On the Clique-Transversal Number in （Claw,K4）-Free 4-Regular Graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted by τC(G),is the minimum cardinality of a clique-transversal set in G.In this paper,we first present a lower bound on τC(G) and characterize the extremal graphs achieving the lower bound for a connected(claw,K4)-free 4-regular graph G.Furthermore,we show that for any 2-connected(claw,K4)-free 4-regular graph G of order n,its clique-transversal number equals to [n/3].     

广义图K(n,m)的点强全色数

图G(V,E)的一个正常k-全染色σ称为G(V,E)的一个k-点强全染色,当且仅当v∈V(G),N[v]中的元素着不同颜色,其中N[v]={u vu∈V(G)}∪{v};并且χvTs(G)=m in{k存在G的一个k-点强全染色}称为G的点强全色数.本文确定了完全图Kn的广义图K(n,m)和乘积图Lm×Kn的点强全色数.     

Hamiltonian results in K1,3-free graphs

There have been a number of results dealing with Hamiltonian properties in powers of graphs. In this paper we show that the square and the total graph of a K_1,3-free graph are vertex pancyclic. We then discuss some of the relationships between connectivity and Hamiltonian properties in K_1,3-free graphs.     

Regular factors in K1,3-free graphs

We show that every connected K_1,3-free graph with minimum degree at least 2k contains a k-factor and construct connected K_1,3-free graphs with minimum degree k + 0(√k) that have no k-factor.     

K3,3-free intersection graphs of finite groups

The intersection graph of a group G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of G, and there is an edge between two distinct vertices H and K if and only if H∩K≠1 where 1 denotes the trivial subgroup of G. In this paper we classify all finite groups whose intersection graphs are K_3,3-free.     

Connected,locally 2-connected,K1,3-free graphs are panconnected

A graph G is locally n-connected, n ≥ 1, if the subgraph induced by the neighborhood of each vertex is n-connected. We prove that every connected, locally 2-connected graph containing no induced subgraph isomorphic to K_1,3 is panconnected.     

On K s -free subgraphs in K s+k -free graphs and vertex Folkman numbers

Extending the problem of determining Ramsey numbers Erdős and Rogers introduced the following function. For given integers 2 ≤ s < t let f _s,t (n) = min{max{|S|: S ⊆ V (H) and H[S] contains no K _s }}, where the minimum is taken over all K _t -free graphs H of order n. This function attracted a considerable amount of attention but despite that, the gap between the lower and upper bounds is still fairly wide. For example, when t=s+1, the best bounds have been of the form Ω(n ^1/2+o(1)) ≤ f _s,s+1(n) ≤ O(n ^1−ɛ(s)), where ɛ(s) tends to zero as s tends to infinity. In this paper we improve the upper bound by showing that f _s,s+1(n) ≤ O(n ^2/3). Moreover, we show that for every ɛ > 0 and sufficiently large integers 1 ≪ k ≪ s, Ω(n ^1/2−ɛ ) ≤ f _s,s+k (n) ≤ O(n ^1/2+ɛ . In addition, we also discuss some connections between the function f _s,t and vertex Folkman numbers.     

On the chromatic number of some P5-free graphs

Let G be a graph. We say that G is perfectly divisible if for each induced subgraph H of G, $V(H)$ can be partitioned into A and B such that $H[A]$ is perfect and $\omega (H[B])<\omega (H)$. We use $P_t$ and $C_t$ to denote a path and a cycle on t vertices, respectively. For two disjoint graphs $F_1$ and $F_2$, we use $F_1\cup F_2$ to denote the graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)$, and use $F_1+F_2$ to denote the graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)\cup \{xy|x\in V(F_1)\text{ and }y\in V(F_2)\}$. In this paper, we prove that (i) $(P_5,C_5,K_{2,3})$-free graphs are perfectly divisible, (ii) $\chi (G)\le 2{\omega }^2(G)?\omega (G)?3$ if G is $(P_5,K_{2,3})$-free with $\omega (G)\ge 2$, (iii) $\chi (G)\le \frac{3}{2}({\omega }^2(G)?\omega (G))$ if G is $(P_5,K_1+2K_2)$-free, and (iv) $\chi (G)\le 3\omega (G)+11$ if G is $(P_5,K_1+(K_1\cup K_3))$-free.     

Longest paths and cycles in K1,3-free graphs

In this article we show that the standard results concerning longest paths and cycles in graphs can be improved for K_1,3-free graphs. We obtain as a consequence of these results conditions for the existence of a hamiltonian path and cycle in K_1,3-free graphs.     

K 4-free graphs without large induced triangle-free subgraphs

Let f _3,4(n), for a natural number n, be the largest integer m such that every K ₄-free graph of order n contains an induced triangle-free subgraph of order m. We prove that for every suffciently large n, f _3,4(n)≤n ^1/2(lnn)¹²⁰. By known results, this bound is tight up to a polylogarithmic factor.     

On the maximal number of certain subgraphs inK r -free graphs

Given two graphsH andG, letH(G) denote the number of subgraphs ofG isomorphic toH. We prove that ifH is a bipartite graph with a one-factor, then for every triangle-free graphG withn verticesH(G) H(T ₂(n)), whereT ₂(n) denotes the complete bipartite graph ofn vertices whose colour classes are as equal as possible. We also prove that ifK is a completet-partite graph ofm vertices,r > t, n max(m, r – 1), then there exists a complete (r – 1)-partite graphG* withn vertices such thatK(G) K(G*) holds for everyK _r -free graphG withn vertices. In particular, in the class of allK _r -free graphs withn vertices the complete balanced (r – 1)-partite graphT _r–1(n) has the largest number of subgraphs isomorphic toK _t (t < r),C ₄,K _2,3. These generalize some theorems of Turán, Erdös and Sauer.Dedicated to Paul Turán on his 80th Birthday     

On partitions of K2,3-free graphs under degree constraints

Suppose that $s$, $t$ are two positive integers, and $?$ is a set of graphs. Let $g(s,t;?)$ be the least integer $g$ such that any $?$-free graph with minimum degree at least $g$ can be partitioned into two sets which induced subgraphs have minimum degree at least $s$ and $t$, respectively. For a given graph $H$, we simply write $g(s,t;H)$ for $g(s,t;?)$ when $?=\left\{H\right\}$. In this paper, we show that if $s,t\ge 2$, then $g(s,t;K_{2,3})\le s+t$ and $g(s,t;\{K_3,C_8,K_{2,3}\})\le s+t?1$. Moreover, if $?$ is the set of graphs obtained by connecting a single vertex to exactly two vertices of $K_4?e$, then $g(s,t;?)\le s+t$ on $?$-free graphs with at least five vertices, which generalize a result of Liu and Xu (2017).     

The homomorphism threshold of -free graphs

We determine the structure of -free graphs with n vertices and minimum degree larger than : such graphs are homomorphic to the graph obtained from a -cycle by adding all chords of length , for some k. This answers a question of Messuti and Schacht. We deduce that the homomorphism threshold of -free graphs is 1/5, thus answering a question of Oberkampf and Schacht.