Clique-Coloring Circular-Arc Graphs

A clique-coloring of a graph is a coloring of its vertices such that no maximal clique of size at least two is monochromatic. A circular-arc graph is the intersection graph of a family of arcs in a circle. We show that every circular-arc graph is 3-clique-colorable. Moreover, we characterize which circular-arc graphs are 2-clique-colorable. Our proof is constructive and gives a polynomial-time algorithm to find an optimal clique-coloring of a given circular-arc graph.     

Paired-Domination in Claw-Free Cubic Graphs

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired-dominating set of G is the paired-domination number of G, denoted by _pr(G). If G does not contain a graph F as an induced subgraph, then G is said to be F-free. In particular if F=K_1,3 or K₄–e, then we say that G is claw-free or diamond-free, respectively. Let G be a connected cubic graph of order n. We show that (i) if G is (K_1,3,K₄–e,C₄)-free, then _pr(G)3n/8; (ii) if G is claw-free and diamond-free, then _pr(G)2n/5; (iii) if G is claw-free, then _pr(G)n/2. In all three cases, the extremal graphs are characterized.Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. This paper was written while the second author was visiting the Laboratoire de Recherche en Informatique (LRI) at the Université de Paris-Sud in July 2002. The second author thanks the LRI for their warm hospitality     

Paired-Domination in Claw-Free Graphs

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number, denoted by γ _pr (G), is the minimum cardinality of a paired-dominating set in G. In this paper we investigate the paired-domination number in claw-free graphs. Specifically, we show that γ _pr (G) ≤ (3n ? 1)/5 if G is a connected claw-free graph of order n with minimum degree at least three and that this bound is sharp.     

Hamiltonian Connected Claw-Free Graphs

A well-known result by O. Ore is that every graph of order n with d(u)+d(v)n+1 for any pair of nonadjacent vertices u and v is hamiltonian connected (i.e., for every pair of vertices, there is a hamiltonian path joining them). In this paper, we show that every 3-connected claw-free graph G on at most 5–8 vertices is hamiltonian connected, where denotes the minimum degree in G. This result generalizes several previous results.Acknowledgments. The author would like to thank the referee for his important suggestions and careful corrections.Final version received: March 12, 2003Supported by the project of Nature Science Funds of China     

Traceability in Small Claw-Free Graphs

We prove that a claw-free, 2-connected graph with fewer than 18 vertices is traceable, and we determine all non-traceable, claw-free, 2-connected graphs with exactly 18 vertices and a minimal number of edges. This complements a result of Matthews on Hamiltonian graphs.     

Hamiltonian Connectedness in Claw-Free Graphs

If every vertex cut of a graph G contains a locally 2-connected vertex, then G is quasilocally 2-connected. In this paper, we prove that every connected quasilocally 2-connected claw-free graph is Hamilton-connected.     

Longest Cycles in Almost Claw-Free Graphs

Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove several properties on longest cycles in almost claw-free graphs. In particular, we show the following two results.? (1) Every 2-connected almost claw-free graph on n vertices contains a cycle of length at least min {n, 2δ+4} and the bound 2δ+ 4 is best possible, thereby fully generalizing a result of Matthews and Sumner.? (2) Every 3-connected almost claw-free graph on n vertices contains a cycle of length at least min {n, 4δ}, thereby fully generalizing a result of MingChu Li. Received: September 17, 1996 Revised: September 22, 1998     

Hamiltonian Cycles in Almost Claw-Free Graphs

 Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove the following two results and conjecture that every 5-connected almost claw-free graph is hamiltonian. (1). Every 2-connected almost claw-free graph G∉J on n≤ 4 δ vertices is hamiltonian, where J is the set of all graphs defined as follows: any graph G in J can be decomposed into three disjoint connected subgraphs G ₁, G ₂ and G ₃ such that E _G (G _i , G _j ) = {u _i , u _j , v _i v _j } for i≠j and i,j = 1, 2, 3 (where u _i ≠v _i ∈V(G _i ) for i = 1, 2, 3). Moreover the bound 4δ is best possible, thereby fully generalizing several previous results. (2). Every 3-connected almost claw-free graph on at most 5δ−5 vertices is hamiltonian, hereby fully generalizing the corresponding result on claw-free graphs. Received: September 21, 1998 Final version received: August 18, 1999     

Distance-Dominating Cycles in Quasi Claw-Free Graphs

We say that a graph G is quasi claw-free if every pair (a ₁, a ₂) of vertices at distance 2 satisfies {u∈N (a ₁)∩N (a ₂) | N[u]⊆N[a ₁]∪N [a ₂]}≠∅. A cycle C is m-dominating if every vertex of G is of distance at most m from C. We prove that if G is a κ-connected (κ≥2) quasi claw-free graph then either G has an m-dominating cycle or G has a set of at least κ+1 vertices such that the distance between every pair of them is at least 2m+3. Received: June 12, 1996 Revised: November 9, 1998     

Semitotal Domination in Claw-Free Cubic Graphs

In this paper, we continue the study of semitotal domination in graphs in [Discrete Math. 324, 13–18 (2014)]. A set \({S}\) of vertices in \({G}\) is a semitotal dominating set of \({G}\) if it is a dominating set of \({G}\) and every vertex in \({S}\) is within distance 2 of another vertex of \({S}\). The semitotal domination number, \({{\gamma_{t2}}(G)}\), is the minimum cardinality of a semitotal dominating set of \({G}\). This domination parameter is squeezed between arguably the two most important domination parameters; namely, the domination number, \({\gamma (G)}\), and the total domination number, \({{\gamma_{t}}(G)}\). We observe that \({\gamma (G) \leq {\gamma_{t2}}(G) \leq {\gamma_{t}}(G)}\). A claw-free graph is a graph that does not contain \({K_{1, \, 3}}\) as an induced subgraph. We prove that if \({G}\) is a connected, claw-free, cubic graph of order \({n \geq 10}\), then \({{\gamma_{t2}}(G) \leq 4n/11}\).     

Tank-Ring Factors in Supereulerian Claw-Free Graphs

A graph G has a tank-ring factor F if F is a connected spanning subgraph with all vertices of degree 2 or 4 that consists of one cycle C and disjoint triangles attaching to exactly one vertex of C such that every component of G ? C contains exactly two vertices. In this paper, we show the following results. (1) Every supereulerian claw-free graph G with 1-hourglass property contains a tank-ring factor. (2) Every supereulerian claw-free graph with 2-hourglass property is Hamiltonian.     

On Hamiltonicity of 3-Connected Claw-Free Graphs

Lai, Shao and Zhan (J Graph Theory 48:142–146, 2005) showed that every 3-connected N ₂-locally connected claw-free graph is Hamiltonian. In this paper, we generalize this result and show that every 3-connected claw-free graph G such that every locally disconnected vertex lies on some induced cycle of length at least 4 with at most 4 edges contained in some triangle of G is Hamiltonian. It is best possible in some sense.     

List-Coloring Claw-Free Graphs with Small Clique Number

Chudnovsky and Seymour proved that every connected claw-free graph that contains a stable set of size 3 has chromatic number at most twice its clique number. We improve this for small clique size, showing that every claw-free graph with clique number at most 3 is 4-choosable and every claw-free graph with clique number at most 4 is 7-choosable. These bounds are tight.     

On a Closure Concept in Claw-Free Graphs

IfGis a claw-free graph, then there is a graphcl(G) such that (i) Gis a spanning subgraph ofcl(G), (ii) cl(G) is a line graph of a triangle-free graph, and (iii) the length of a longest cycle inGand incl(G) is the same. A sufficient condition for hamiltonicity in claw-free graphs, the equivalence of some conjectures on hamiltonicity in 2-tough graphs and the hamiltonicity of 7-connected claw-free graphs are obtained as corollaries.     

On the Choosability of Claw-Free Perfect Graphs

It has been conjectured that for every claw-free graph G the choice number of G is equal to its chromatic number. We focus on the special case of this conjecture where G is perfect. Claw-free perfect graphs can be decomposed via clique-cutset into two special classes called elementary graphs and peculiar graphs. Based on this decomposition we prove that the conjecture holds true for every claw-free perfect graph with maximum clique size at most 4.     

3－连通正则无爪图的Hamilton圈

本文证明了：任一阶数不超过６ｋ—４的３－连通ｋ－正则无爪图是Ｈａｍｉｌｔｏｎ的．     

A Twelve Vertex Theorem for 3-Connected Claw-Free Graphs

The cyclability of a graph H, denoted by C(H), is the largest integer r such that H has a cycle through any r vertices. For a claw-free graph H, by Ryjá?ek (J Comb Theory Ser B 70:217–224, 1997) closure concept, there is a \(K_3\)-free graph G such that the closure \(cl(H)=L(G)\). In this note, we prove that for a 3-connected claw-free graph H with its closure \(cl(H)=L(G)\), \(C(H)\ge 12\) if and only if G can not be contracted to the Petersen graph in such a way that each vertex in P is obtained by contracting a nontrivial connected \(K_3\)-free subgraph. This is an improvement of the main result in Györi and Plummer (Stud Sci Math Hung 38:233–244, 2001).