Search

Let G be a 2-connected claw-free graph on n vertices. For a vertex v ∈ V (G) and an integer r ≥ 1 , M r (v) denotes the set of vertices of G whose distances from v do not exceed r. Matthews and Sumner in 1985 proved that G is hamiltonian if d (v) ≥ n - 2 3 for every vertex v ∈ V (G) . In this paper we pay attention to localize the above Matthews-Sumner’s degree condition by determining the minimum integer r such that G is hamiltonian if d (v) ≥ | M r (v) | - 2 3 for every vertex v ∈ V (G) . While we conjecture that r = 3 is best possible, we settle the case r = 4 . In fact, we obtain a strong result that G is hamiltonian if d (v) ≥ | M 4 (v) | - 2 3 for every vertex v that is an end-vertex of an induced copy of a net, which is a graph obtained from a triangle by adding three disjoint pendant edges. This generalizes a result of Chen which states that G is hamiltonian if d (v) ≥ n - 2 3 for every vertex v that is an end-vertex of an induced copy of a net. [ABSTRACT FROM AUTHOR]

If a graph G contains two spanning trees T 1 , T 2 such that for each two distinct vertices x , y of G , the (x , y) -path in each T i has no common edge and no common vertex except for the two ends, then T 1 , T 2 are called two completely independent spanning trees (CISTs) of G , i ∈ { 1 , 2 }. There are several results on the existence of two CISTs. In this paper, we prove that every 2-connected {claw, Z 2 }-free graph with minimum degree at least 4 contains two CISTs. The bound of the minimum degree in our result is best possible. [ABSTRACT FROM AUTHOR]

A kernel of a directed graph is a subset of vertices that is both independent and absorbing (every vertex not in the kernel has an out-neighbour in the kernel). Not all directed graphs contain kernels, and computing a kernel or deciding that none exist is NP -complete even on low-degree planar digraphs. The existing polynomial-time algorithms for this problem are all obtained by restricting both the undirected structure and the edge orientations of the input: for example, to chordal graphs without bidirectional edges (Pass-Lanneau, Igarashi and Meunier, Discrete Appl Math 2020) or to permutation graphs where each clique has a sink (Abbas and Saoula, 4OR 2005). By contrast, we count the kernels of a fuzzy circular interval graph in polynomial time, regardless of its edge orientations, and return a kernel when one exists. (Fuzzy circular interval graphs were introduced by Chudnovsky and Seymour in their structure theorem for claw-free graphs.) We also consider kernels on cographs, where we establish NP -hardness in general but linear-time solvability on the subclass of threshold graphs. [ABSTRACT FROM AUTHOR]

We study the problem of finding a maximum-cardinality set of r -cliques in an undirected graph of fixed maximum degree Δ , subject to the cliques in that set being either vertex disjoint or edge disjoint. It is known for r = 3 that the vertex-disjoint (edge-disjoint) problem is solvable in linear time if Δ = 3 (Δ = 4) but APX -hard if Δ ≥ 4 (Δ ≥ 5). We generalise these results to an arbitrary but fixed r ≥ 3 , and provide a complete complexity classification for both the vertex- and edge-disjoint variants in graphs of maximum degree Δ. Specifically, we show that the vertex-disjoint problem is solvable in linear time if Δ < 3 r / 2 − 1 , solvable in polynomial time if Δ < 5 r / 3 − 1 , and APX -hard if Δ ≥ ⌈ 5 r / 3 ⌉ − 1. We also show that if r ≥ 6 then the above implications also hold for the edge-disjoint problem. If r ≤ 5 , then the edge-disjoint problem is solvable in linear time if Δ < 3 r / 2 − 1 , solvable in polynomial time if Δ ≤ 2 r − 2 , and APX -hard if Δ > 2 r − 2. [ABSTRACT FROM AUTHOR]

A 3-star is a complete bipartite graph K 1 , 3 . A 3-star packing of a graph G is a collection of vertex-disjoint subgraphs of G in which each subgraph is a 3-star. The maximum 3-star packing problem is to find a 3-star packing of a given graph with the maximum number of 3-stars. A 2-independent set of a graph G is a subset S of V(G) such that for each pair of vertices u , v ∈ S , paths between u and v are all of length at least 3. In cubic graphs, the maximum 3-star packing problem is equivalent to the maximum 2-independent set problem. The maximum 2-independent set problem was proved to be NP-hard on cubic graphs (Kong and Zhao in Congressus Numerantium 143:65–80, 2000), and the best approximation algorithm of maximum 2-independent set problem for cubic graphs has approximation ratio 8 15 (Miyano et al. in WALCOM 2017, Proceedings, pp 228–240). In this paper, we first prove that the maximum 3-star packing problem is NP-hard in claw-free cubic graphs and then design a linear-time algorithm which can find a 3-star packing of a connected claw-free cubic graph G covering at least 3 v (G) - 8 4 vertices, where v(G) denotes the number of vertices of G. [ABSTRACT FROM AUTHOR]

Let I(G; x) denote the independence polynomial of a graph G. Alavi, Malde, Schwenk and Erdős conjectured for any tree T that I(T; x) is unimodal. In this paper, we derive that rooted products of some trees preserve real-rootedness of independence polynomials. In consequence, we obtain more and more trees whose independence polynomials have only real zeros. This in particular implies that their independence polynomials are unimodal. [ABSTRACT FROM AUTHOR]

An edge e in a matching covered graph G is removable if G - e is matching covered. Removable edges were introduced by Lovász and Plummer in connection with ear decompositions of matching covered graphs. A brick is a non-bipartite matching covered graph without non-trivial tight cuts. The importance of bricks stems from the fact that they are building blocks of matching covered graphs. Lovász proved that every brick other than K 4 and C 6 ¯ has a removable edge. It is known that every 3-connected claw-free graph with even number of vertices is a brick. By characterizing the structure of adjacent non-removable edges, we show that every claw-free brick G with more than 6 vertices has at least 5|V(G)|/8 removable edges. [ABSTRACT FROM AUTHOR]

An independent set in a graph G is a set of pairwise non-adjacent vertices. The independence polynomial of G is the polynomial ∑ A x ∣ A ∣ , where the sum is over all independent sets A of G. In 1987, Alavi, Malde, Schwenk and Erdős conjectured that the independence polynomial of any tree or forest is unimodal. Although this unimodality conjecture has attracted many researchers' attention, it is still open. Recently, Basit and Galvin even asked a much stronger question whether the independence polynomial of every tree is ordered log-concave. Note that if a polynomial has only negative real zeros then it is ordered log-concave and unimodal. In this paper, we observe real-rootedness of independence polynomials of rooted products of graphs. We find some trees whose rooted product preserves real-rootedness of independence polynomials. In consequence, starting from any graph whose independence polynomial has only real zeros, we can obtain an infinite family of graphs whose independence polynomials have only real zeros. In particular, applying it to trees or forests, we obtain that their independence polynomials are unimodal and ordered log-concave. [ABSTRACT FROM AUTHOR]

Let t be a positive real number. A graph is called t-tough if the removal of any vertex set S that disconnects the graph leaves at most |S|/t components, and all graphs are considered 0-tough. The toughness of a graph is the largest t for which the graph is t-tough, whereby the toughness of complete graphs is defined as infinity. A graph is minimally t-tough if the toughness of the graph is t, and the deletion of any edge from the graph decreases the toughness. In this paper, we investigate the minimum degree and the recognizability of minimally t-tough graphs in the classes of chordal graphs, split graphs, claw-free graphs, and 2K2-free graphs. [ABSTRACT FROM AUTHOR]

Let G = (V(G), E(G)) be a graph. A function f : V(G) → ℙ({1, 2}) is a 2-rainbow dominating function if for every vertex v with f(v) = ∅, f(N(v)) = {1, 2}. An outer-independent 2-rainbow dominating function (OI2RD function) of G is a 2-rainbow dominating function f for which the set of all v 2208 V(G) with f(v) = ∅ is independent. The outer independent 2-rainbow domination number (OI2RD number) γoir2(G) is the minimum weight of an OI2RD function of G. In this paper, we first prove that n/2 is a lower bound on the OI2RD number of a connected claw-free graph of order n and characterize all such graphs for which the equality holds, solving an open problem given in an earlier paper. In addition, a study of this parameter for some graph products is carried out. In particular, we give a closed (resp. an exact) formula for the OI2RD number of rooted (resp. corona) product graphs and prove upper bounds on this parameter for the Cartesian product and direct product of two graphs. [ABSTRACT FROM AUTHOR]

The subject of this work is the study of LS + -perfect graphs defined as those graphs G for which the stable set polytope STAB (G) is achieved in one iteration of Lovász–Schrijver PSD-operator LS + , applied to its edge relaxation ESTAB (G). The recently formulated LS + -Perfect Graph Conjecture aims at a characterization of this family of graphs, through the structure of the facet defining inequalities of the stable set polytope. The main contribution of this work is to verify it for the well-studied class of claw-free graphs. [ABSTRACT FROM AUTHOR]

A graph is balanced when its clique matrix is balanced. Bonomo, Durán, Lin and Szwarcfiter (2006) proved that a graph is balanced if and only if it contains no induced subgraphs known as extended odd suns. However, a characterization of balanced graphs by minimal forbidden induced subgraphs is not known. In this work, we find such a characterization when restricted to the class of claw-free graphs. As a consequence, we prove that there is an O(m2 + n)-time algorithm that, given any graph, either decides that it is balanced or gives a certificate of the fact that it is not claw-free balanced. [ABSTRACT FROM AUTHOR]

A graph G is called an odd (even) graph if for every vertex v ∈ V (G), dG (v) is odd (even). Let G be a graph of even order. Scott in 1992 proved that the vertices of every connected graph of even order can be partitioned into some odd induced forests. We denote the minimum number of odd induced subgraphs which partition V (G) by od(G). If all of the subgraphs are forests, then we denote it by odF (G). In this paper, we show that if G is a connected subcubic graph of even order or G is a connected planar graph of even order, then odF (G) ≤ 4. Moreover, we show that for every tree T of even order odF (T) ≤ 2 and for every unicyclic graph G of even order odF (G) ≤ 3. Also, we prove that if G is claw-free, then V (G) can be partitioned into at most Δ(G)-1 induced forests and possibly one independent set. Furthermore, we demonstrate that the vertex set of the line graph of a tree can be partitioned into at most two odd induced subgraphs and possibly one independent set. [ABSTRACT FROM AUTHOR]

The harmonic index H (G) of a graph G is ∑ u v ∈ E (G) 2 d (u) + d (v) , where d (v) is the degree of v ∈ V (G). We show that H (L (T)) > n 4 for any tree T of order n ≥ 3 , which confirm the validity of a conjecture proposed by Zhang and Wu. In addition, the same lower bound holds for a unicyclic graph G of order n. Two relevant conjectures are proposed as well. [ABSTRACT FROM AUTHOR]

A Helly circular-arc graph is the intersection graph of a set of arcs on a circle having the Helly property. We introduce essential obstacles, which are a refinement of the notion of obstacles, and prove that essential obstacles are precisely the minimal forbidden induced circular-arc subgraphs for the class of Helly circular-arc graphs. We show that it is possible to find in linear time, in any given obstacle, some minimal forbidden induced subgraph for the class of Helly circular-arc graphs contained as an induced subgraph. Moreover, relying on an existing linear-time algorithm for finding induced obstacles in circular-arc graphs, we conclude that it is possible to find in linear time an induced essential obstacle in any circular-arc graph that is not a Helly circular-arc graph. The problem of finding a forbidden induced subgraph characterization, not restricted only to circular-arc graphs, for the class of Helly circular-arc graphs remains unresolved. As a partial answer to this problem, we find the minimal forbidden induced subgraph characterization for the class of Helly circular-arc graphs restricted to graphs containing no induced claw and no induced 5-wheel. Furthermore, we show that there is a linear-time algorithm for finding, in any given graph that is not a Helly circular-arc graph, an induced subgraph isomorphic to claw, 5-wheel, or some minimal forbidden induced subgraph for the class of Helly circular-arc graphs. [ABSTRACT FROM AUTHOR]

The QE constant of a finite connected graph G, denoted by QEC(G), is by definition the maximum of the quadratic function associated to the distance matrix on a certain sphere of codimension two. We prove that the QE constants of paths Pn form a strictly increasing sequence converging to −1/2. Then we formulate the problem of determining all the graphs G satisfying QEC(Pn)≤QEC(G)

Let be the total domination number and let be the total domination subdivision number of a graph G with no isolated vertex. In this paper, we show that for some classes of graphs G, which partially solve the conjecture presented by Favaron et al.

In this paper, we give a series of counterexamples to negate a conjecture and answer an open question on the k-power domination of regular graphs [see Dorbec et al. (SIAM J Discrete Math 27:1559–1574, 2013)]. Furthermore, we focus on the study of k-power domination of claw-free graphs. We show that for l ∈ { 2 , 3 } and k ≥ l , the k-power domination number of a connected claw-free (k + l + 1) -regular graph on n vertices is at most n k + l + 2 , and this bound is tight. [ABSTRACT FROM AUTHOR]

The Randić index of a graph G, denoted by R (G) , is defined as the sum of 1 / d (u) d (v) for all edges u v of G, where d (u) denotes the degree of a vertex u in G. In this note, we show that R (L (T)) > n 4 for any tree T of order n ≥ 3 . A number of relevant conjectures are proposed. [ABSTRACT FROM AUTHOR]

In this paper, we discuss various connections between the smallest eigenvalue of the adjacency matrix of a graph and its structure. There are several techniques for obtaining upper bounds on the smallest eigenvalue, and some of them are based on Rayleigh quotients, Cauchy interlacing using induced subgraphs, and Haemers interlacing with vertex partitions and quotient matrices. In this paper, we are interested in obtaining lower bounds for the smallest eigenvalue. Motivated by results on line graphs and generalized line graphs, we show how graph decompositions can be used to obtain such lower bounds.

A b-coloring of a graph is a proper coloring of its vertices such that each color class contains a vertex adjacent to at least one vertex of every other color class. The b-chromatic number of a graph is the largest integer k such that the graph has a b-coloring with k colors. In this work we present lower bounds for the b-chromatic number of a vertex-deleted subgraph of a graph, particularly regarding two important classes, claw-free graphs and chordal graphs. We also get bounds for the b-chromatic number of G − { x } , when G is a graph with large girth. [ABSTRACT FROM AUTHOR]

For a graph G = (V (G) , E (G)) , an Italian dominating function (ID function) of G is a function f : V (G) → { 0 , 1 , 2 } such that for each vertex v ∈ V (G) with f (v) = 0 , f (N (v)) ≥ 2 , that is, either there is a vertex u ∈ N (v) with f (u) = 2 or there are two vertices x , y ∈ N (v) with f (x) = f (y) = 1. A function f : V (G) → { 0 , 1 , 2 } is a covering Italian dominating function (CID function) of G if f is an ID function and { v ∈ V (G) ∣ f (v) ≠ 0 } is a vertex cover set. The covering Italian domination number (CID number) γ c I (G) is the minimum weight taken over all CID functions of G. In this paper, we study the CID number in graphs. We show that the problem of computing this parameter is NP-hard even when restricted to some well-known families of graphs, and find some bounds on this parameter. We characterize the family of graphs for which their CID numbers attain the upper bound twice their vertex cover number as well as all claw-free graphs whose CID numbers attain the lower bound half of their orders. We also give the characterizations of some families of graphs with small CID numbers. [ABSTRACT FROM AUTHOR]

A total coloring of a graph is an assignment of colors to all the elements (vertices and edges) of the graph such that no two adjacent or incident elements receive the same color. A claw-free graph is a graph that does not have K 1 , 3 as an induced subgraph. Quasi-line and inflated graphs are two well-known classes of claw-free graphs. In this paper, we prove that the quasi-line and inflated graphs are totally colorable. In particular, we prove the tight bound of the total chromatic number of some classes of quasi-line graphs and inflated graphs. [ABSTRACT FROM AUTHOR]

A set S ⊆ V of a graph G = (V , E) is a dominating set if each vertex has a neighbor in S or belongs to S. Dominating Set is the problem of deciding, given a graph G and an integer k ≥ 1 , if G has a dominating set of size at most k. It is well known that this problem is NP -complete even for claw-free graphs. We give a (almost) complexity dichotomy for Dominating Set for the class of claw-free graphs with diameter d. We show that the problem is NP -complete for every fixed d ≥ 3 and polynomial-time solvable for d ≤ 2. To prove the case d = 2 , we show that Minimum Maximal Matching can be solved in polynomial-time for 2 K 2 -free graphs. [ABSTRACT FROM AUTHOR]

A graph is strongly perfect if every induced subgraph H of it has a stable set that meets every maximal clique of H. A graph is claw‐free if no vertex has three pairwise nonadjacent neighbors. The characterization of claw‐free graphs that are strongly perfect by a set of forbidden induced subgraphs was conjectured by Ravindra in 1990 and was proved by Wang in 2006. Here we give a shorter proof of this characterization. [ABSTRACT FROM AUTHOR]

The maximum weighted stable set problem in claw-free graphs is a well-known generalization of the maximum weighted matching problem, and a classical problem in combinatorial optimization. In spite of the recent development of fast(er) combinatorial algorithms and some progresses in the characterization of the corresponding stable set polytope, the problem of "providing a decent linear description" for this polytope (Grötschel et al. in Geometric algorithms and combinatorial optimization, Springer, New York, 1988) is still open. The main contribution of this paper is to propose an algorithmic answer to that question by providing a polynomial-time and computationally attractive separation routine for the stable set polytope of claw-free graphs, that only requires a combinatorial decomposition algorithm, the solution of (moderate sized) compact linear programs, and Padberg and Rao's algorithm for separating over the matching polytope. In particular, it is a generalization of the latter and avoids the heavy computational burden of resorting to the ellipsoid method, on which the only poly-time separation routine known so far relied. Besides, our separation routine comes with a 'small' (but not polynomial) extended linear programming formulation and a procedure to derive a linear description of the stable set polytope of claw-free graphs in the original space. [ABSTRACT FROM AUTHOR]

The complete bipartite graph K 1 , 3 is called a claw. A graph is said to be claw-free if it contains no induced subgraph isomorphic to a claw. Given a graph G, the NP-hard Graph Declawing Problem (GDP) consists of finding a minimum set S ⊆ V (G) such that G - S is claw-free. This work develops a polyhedral study of the GDP polytope, expliciting its full dimensionality, proposing and testing five families of facets: trivial inequalities, claw inequalities, star inequalities, lantern inequalities, and binary star inequalities. In total, four Branch-and-Cut algorithms with separation heuristics have been developed to test the computational benefits of each proposed family on random graph instances and random interval graph instances. Our results show that the model that uses a separation heuristics proposed for star inequalities achieves better results on both set of instances in almost all cases. [ABSTRACT FROM AUTHOR]

The QE constant of a finite connected graph G, denoted by QEC(G), is by definition the maximum of the quadratic function associated to the distance matrix on a certain sphere of codimension two. We prove that the QE constants of paths Pn form a strictly increasing sequence converging to -1/2. Then we formulate the problem of determining all the graphs G satisfying QEC(Pn) = QEC(G) < QEC(Pn+1). The answer is given for n = 2 and n = 3 by exploiting forbidden subgraphs for QEC(G) < -1/2 and the explicit QE constants of star products of the complete graphs. [ABSTRACT FROM AUTHOR]

The edge clique cover number ecc(G) of a graph G is the size of the smallest collection of complete subgraphs whose union covers all edges of G. Chen, Jacobson, Kézdy, Lehel, Scheinerman, and Wang conjectured in 2000 that if G is claw‐free, then ecc(G) is bounded above by its order (denoted n). Recently, Javadi and Hajebi verified this conjecture for claw‐free graphs with an independence number at least three. We study the edge clique cover number of graphs with independence number two, which are necessarily claw‐free. We give the first known proof of a linear bound in n for ecc(G) for such graphs, improving upon the bou nd of O(n4∕3log1∕3 n) due to Javadi, Maleki, and Omoomi. More precisely we prove that ecc(G) is at most the minimum of n+δ(G) and 2n−Ω(nlog n), where δ(G) is the minimum degree of G. In the fractional version of the problem, we improve these upper bounds to 32n. We also verify the conjecture for some specific subfamilies, for example, when the edge packing number with respect to cliques (a lower bound for ecc(G)) equals n, and when G contains no induced subgraph isomorphic to H where H is any fixed graph of order 4. [ABSTRACT FROM AUTHOR]

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(|V|(|E|+|V| log |V|))-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which is also introduced in the present article. Despite being weaker than the structural results for claw-free graphs given by Chudnovsky and Seymour [2005, 2008a, 2008b] our decomposition theorem is, on the other hand, algorithmic, that is, it is coupled with an O(|V||E|)-time algorithm that actually produces the decomposition. [ABSTRACT FROM AUTHOR]

The connected graph of degree sequence 3, 3, 3, 1, 1, 1 is called a net, and the vertices of degree 1 in a net are called its endvertices. Broersma conjectured in 1993 that a 2-connected graph G with no induced K 1 , 3 is hamiltonian if every endvertex of each induced net of G has degree at least (| V (G) | - 2) / 3 . In this paper we prove this conjecture in the affirmative. [ABSTRACT FROM AUTHOR]

A graph G(V, E) is claw-free if no vertex has three pairwise non-adjacent neighbours. The maximum weight stable set (MWSS) problem in a claw-free graph is a natural generalization of the matching problem and has been shown to be polynomially solvable by Minty and Sbihi in 1980. In a remarkable paper, Faenza, Oriolo and Stauffer have shown that, in a two-step procedure, a claw-free graph can be first turned into a quasi-line graph by removing strips containing all the irregular nodes and then decomposed into {claw, net}-free strips and strips with stability number at most three. Through this decomposition, the MWSS problem can be solved in O (| V | (| V | log | V | + | E |)) time. In this paper, we describe a direct decomposition of a claw-free graph into {claw, net}-free strips and strips with stability number at most three which can be performed in O (| V | 2) time. In two companion papers we showed that the MWSS problem can be solved in O (| E | log | V |) time in claw-free graphs with α (G) ≤ 3 and in O (| V | | E |) time in {claw, net}-free graphs with α (G) ≥ 4 . These results prove that the MWSS problem in a claw-free graph can be solved in O (| V | 2 log | V |) time, the same complexity of the best and long standing algorithm for the MWSS problem in line graphs. [ABSTRACT FROM AUTHOR]

The first combinatorial algorithm for the minimum weighted clique cover (MWCC) in a claw‐free perfect graph G due to Hsu and Nemhauser dates back to 1984. It is essentially a "dual" algorithm as it relies on any algorithm for the maximum weighted stable set (MWSS) problem in claw‐free graphs and, taking into account the best‐known complexity for the latter problem, its complexity is O(∣V(G)∣5). More recently, Chudnovsky and Seymour introduced a composition operation, strip composition, to define their structural results for claw‐free graphs; however, this composition operation is general and applies to nonclaw‐free graphs as well. In this paper, we show that an MWCC of a perfect strip‐composed graph, with the basic graphs belonging to a class G, can be found in polynomial time, provided that the MWCC problem can be solved on G in polynomial time. For the case of claw‐free perfect strip‐composed graphs, the algorithm can be tailored so that it never requires the computation of an MWSS on the strips and can be implemented as to run in O(∣V(G)∣3) time. Finally, building upon several results from the literature, we show how to deal with nonstrip‐composed claw‐free perfect graphs, and therefore compute an MWCC in a general claw‐free perfect graph in O(∣V(G)∣3) time. [ABSTRACT FROM AUTHOR]

A clique-coloring of a given graph G is a coloring of the vertices of G such that no maximal clique of size at least two is monocolored. The clique-chromatic number of G is the least number of colors for which G admits a clique-coloring. It has been proved that every planar graph is 3-clique colorable and every claw-free planar graph, different from an odd cycle, is 2-clique colorable. In this paper, we generalize these results to K 3 , 3 -minor free ( K 3 , 3 -subdivision free) graphs. [ABSTRACT FROM AUTHOR]

In 1987, Alavi, Malde, Schwenk and Erdős conjectured that the independence polynomial of any tree is unimodal. Although it attracts many researchers' attention, it is still open. Motivated by this conjecture, in this paper, we prove that rooted products of some graphs preserve real rootedness of independence polynomials. As application, we not only give a unified proof for some known results, but also we can apply them to generate infinite kinds of trees whose independence polynomials have only real zeros. Thus their independence polynomials are unimodal. [ABSTRACT FROM AUTHOR]

A strong edge-coloring of a graph G is a coloring of the edges of G such that each color class is an induced matching. The strong chromatic index of G is the minimum number of colors in a strong edge-coloring of G. We show that the strong chromatic index of a claw-free graph with maximum degree Δ is at most 1. 125 Δ 2 + Δ , which confirms the conjecture of Erdős and Nešetřil from 1985 for this class of graphs for Δ ≥ 12. We also prove an upper bound of 2 − 1 t − 2 Δ 2 on strong chromatic index of K 1 , t -free graphs with maximum degree Δ for all t ≥ 4 and give an improved result 1. 625 Δ 2 for unit disk graphs. [ABSTRACT FROM AUTHOR]

A partition of the vertex set of a graph G into k independent sets V 1 , V 2 , ... , V k is called a k -class domination coloring (k -cd-coloring) of G if for every V i , 1 ≤ i ≤ k , there exists a vertex x i such that V i ⊆ N x i . For a given graph G and a positive integer k , the cd-colorability problem, CD-Colorability , is to decide whether G admits a k -cd-coloring. This problem is NP-complete, even for bipartite graphs. In this paper, we study the complexity of this problem on several natural graph classes. We prove that CD-Colorability is NP-complete for chordal graphs. We also obtain the following dichotomy results: (i) CD-Colorability is NP-complete for graphs with α (G) ≥ 3 and is polynomial time solvable for graphs with α (G) ≤ 2 ; (ii) CD-Colorability of K 1 , p -free graphs is NP-complete for p ≥ 4 and is polynomial time solvable for p ≤ 3 ; (iii) CD-Colorability for the class of H -free graphs is polynomial time solvable if H is an induced subgraph of P 4 or P 3 ∪ K 1 or K 1 , 3 and NP-complete for any other H. We present polynomial time algorithms for the classes of claw-free graphs, P 4 -free graphs, and double-split graphs. We also characterize the class of all 3-cd-colorable graphs and thereby improve the time complexity of an algorithm of Merouane et al. (2015) for recognizing 3-cd-colorable graphs from O (n 6) to O (n 5) , where n = | V (G) |. [ABSTRACT FROM AUTHOR]

A total coloring of a graph is an assignment of colors to all the elements of the graph such that no two adjacent or incident elements receive the same color. A graph G is prismatic, if for every triangle T , every vertex not in T has exactly one neighbor in T. In this paper, we prove the total coloring conjecture (TCC) for prismatic graphs and the tight bound of the TCC for some classes of prismatic graphs. [ABSTRACT FROM AUTHOR]

We study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, nonetheless, we identify restrictions to the problem where it either remains NP-complete or has a polynomial time algorithm. First, we characterize the possibility of when an Aztec rectangle and an Aztec diamond has an L-tromino tiling. Then, we study tilings of arbitrary regions where only 180 ∘ rotations of L-trominoes are available. For this particular case we show that deciding the existence of a tiling remains NP-complete; yet, if a region does not contain certain so-called "forbidden polyominoes" as sub-regions, then there exists a polynomial time algorithm for deciding a tiling. [ABSTRACT FROM AUTHOR]

For an integer s ≥ 0 , a graph G is s -hamiltonian if for any vertex subset S ⊆ V (G) with | S | ≤ s , G − S is hamiltonian, and G is s -hamiltonian connected if for any vertex subset S ⊆ V (G) with | S | ≤ s , G − S is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Kučzel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjáček and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of s -hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for s ≥ 2 , a line graph L (G) is s -hamiltonian if and only if L (G) is (s + 2) -connected. In this paper we prove the following. (i) For an integer s ≥ 2 , the line graph L (G) of a claw-free graph G is s -hamiltonian if and only if L (G) is (s + 2) -connected. (ii) The line graph L (G) of a claw-free graph G is 1-hamiltonian connected if and only if L (G) is 4-connected. [ABSTRACT FROM AUTHOR]

Using a graph and its colorings we can define a chromatic symmetric function. Stanley's celebrated conjecture about the e-positivity of claw-free incomparability graphs has seen several related results, including one showing ( c l a w , P 4 )-free graphs are e-positive. Here we extend the claw-free idea to general graphs and consider the e-positivity question for H-free graphs where H = { c l a w , F } and H = {claw, F, co-F}, where F is a four-vertex graph. We settle the question for all cases except H = {claw, co-diamond}, and we provide some partial results in that case. [ABSTRACT FROM AUTHOR]

The smallest number of cliques, covering all edges of a graph G, is called the (edge) clique cover number of G and is denoted by cc(G). It is an easy observation that if G is a line graph on n vertices, then cc(G)≤n. G. Chen et al. [Discrete Math. 219 (2000), no. 1–3, 17–26; MR1761707] extended this observation to all quasi‐line graphs and questioned if the same assertion holds for all claw‐free graphs. In this paper, using the celebrated structure theorem of claw‐free graphs due to Chudnovsky and Seymour, we give an affirmative answer to this question for all claw‐free graphs with independence number at least three. In particular, we prove that if G is a connected claw‐free graph on n vertices with three pairwise nonadjacent vertices, then cc(G)≤n and the equality holds if and only if G is either the graph of icosahedron, or the complement of a graph on 10 vertices called "twister" or the pth power of the cycle Cn, for some positive integer p≤⌊(n−1)∕3⌋. [ABSTRACT FROM AUTHOR]