BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Given two graphs H1 and H2, a graph G is (H1,H2)-free if it contains no induced subgraph isomorphic to H1 or H2. A Pt is the path on t vertices. A chair is a P4 with an additional vertex adjacent to one of the middle vertices of the P4. 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. In this paper, we prove that there are finitely many 5-vertex-critical (P5,chair)-free graphs.
Let Pn and Kn denote the induced path and complete graph on n vertices, respectively. The {\em kite} is the graph obtained from a P4 by adding a vertex and making it adjacent to all vertices in the P4 except one vertex with degree 1. A graph is (P5, kite)-free if it has no induced subgraph isomorphic to a P5 or a kite. For a graph G, the chromatic number of G (denoted by χ(G)) is the minimum number of colors needed to color the vertices of G such that no two adjacent vertices receive the same color, and the clique number of G is the size of a largest clique in G. Here, we are interested in the class of (P5, kite)-free graphs with small clique number. It is known that every (P5,~kite, K3)-free graph G satisfies χ(G)≤3, every (P5,~kite, K4)-free graph G satisfies χ(G)≤4, and that every (P5,~kite, K5)-free graph G satisfies χ(G)≤6. In this paper, we showed the following: ∙ Every (P5, kite, K6)-free graph G satisfies χ(G)≤7. ∙ Every (P5, kite, K7)-free graph G satisfies χ(G)≤9. We also give examples to show that the above bounds are tight.
Given two graphs H1 and H2, a graph G is (H1,H2)-free if it contains no induced subgraph isomorphic to H1 or H2. Let Pt 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 P5-free graphs. Our main result is a complete classification of the finiteness of k-vertex-critical graphs in the class of (P5,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 Dilworth's Theorem -- that may be of independent interest.
The χ-stability index esχ(G) of a graph G is the minimum number of its edges whose removal results in a graph with the chromatic number smaller than that of G. In this paper three open problems from [European J.\ Combin.\ 84 (2020) 103042] are considered. Examples are constructed which demonstrate that a known characterization of k-regular (k≤5) graphs G with esχ(G)=1 does not extend to k≥6. Graphs G with χ(G)=3 for which esχ(G)+esχ(G)=2 holds are characterized. Necessary conditions on graphs G which attain a known upper bound on esχ(G) in terms of the order and the chromatic number of G are derived. The conditions are proved to be sufficient when n≡2(mod3) and χ(G)=3.
A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, and more generally, (cap, 4-hole)-free odd-signable graphs. We give an explicit construction of these graphs. We prove that every such graph G has a vertex of degree at most 23ω(G)−1, and hence χ(G)≤23ω(G), where ω(G) denotes the size of a largest clique in G and χ(G) denotes the chromatic number of G. We give an O(nm) algorithm for q-coloring these graphs for fixed q and an O(nm) algorithm for maximum weight stable set. We also give a polynomial-time algorithm for minimum coloring. Our algorithms are based on our results that triangle-free odd-signable graphs have treewidth at most 5 and thus have clique-width at most 48, and that (cap, 4-hole)-free odd-signable graphs G without clique cutsets have treewidth at most 6ω(G)−1 and clique-width at most 48.
A {\em hole} is a chordless cycle of length at least four. A hole is {\em even} (resp. {\em odd}) if it contains an even (resp. odd) number of vertices. A \emph{cap} is a graph induced by a hole with an additional vertex that is adjacent to exactly two adjacent vertices on the hole. In this note, we use a decomposition theorem by Conforti et al. (1999) to show that if a graph G does not contain any even hole or cap as an induced subgraph, then χ(G)≤⌊23ω(G)⌋, where χ(G) and ω(G) are the chromatic number and the clique number of G, respectively. This bound is attained by odd holes and the Hajos graph. The proof leads to a polynomial-time 3/2-approximation algorithm for coloring (even-hole,cap)-free graphs.
Given two graphs H1 and H2, a graph G is (H1,H2)-free if it contains no subgraph isomorphic to H1 or H2. We continue a recent study into the clique-width of (H1,H2)-free graphs and present three new classes of (H1,H2)-free graphs of bounded clique-width and one of unbounded clique-width. The four new graph classes have in common that one of their two forbidden induced subgraphs is the diamond (the graph obtained from a clique on four vertices by deleting one edge). To prove boundedness of clique-width for the first three cases we develop a technique based on bounding clique covering number in combination with reduction to subclasses of perfect graphs. We extend our proof of unboundedness for the fourth case to show that Graph Isomorphism is Graph Isomorphism-complete on the same graph class. We also show the implications of our results for the computational complexity of the Colouring problem restricted to (H1,H2)-free graphs.
A graph is H-free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandstädt, Le and Mosca erroneously claimed that the gem and the co-gem are the only two 1-vertex P4-extensions H for which the class of H-free chordal graphs has bounded clique-width. In fact we prove that bull-free chordal and co-chair-free chordal graphs have clique-width at most 3 and 4, respectively. In particular, we find four new classes of H-free chordal graphs of bounded clique-width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H-free chordal graphs has bounded clique-width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of (2P1+P3,K4)-free graphs has bounded clique-width via a reduction to K4-free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique-width of H-free weakly chordal graphs.
A graph is H-free if it has no induced subgraph isomorphic to H. We continue a study into the boundedness of clique-width of subclasses of perfect graphs. We identify five new classes of H-free split graphs whose clique-width is bounded. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H-free split graphs has bounded clique-width.
For a positive integer k and graph G=(V,E), a k-colouring of G is a mapping c:V→{1,2,…,k} such that c(u)=c(v) whenever uv∈E. The k-Colouring problem is to decide, for a given G, whether a k-colouring of G exists. The k-Precolouring Extension problem is to decide, for a given G=(V,E), whether a colouring of a subset of V can be extended to a k-colouring of G. A k-list assignment of a graph is an allocation of a list -a subset of {1,…,k}- to each vertex, and the List k-Colouring problem is to decide, for a given G, whether G has a k-colouring in which each vertex is coloured with a colour from its list. We continued the study of the computational complexity of these three decision problems when restricted to graphs that contain neither a cycle on s vertices nor a path on t vertices as induced subgraphs (for fixed positive integers s and~t).
Let Pt and Cℓ denote a path on t vertices and a cycle on ℓ vertices, respectively. In this paper we study the k-coloring problem for (Pt,Cℓ)-free graphs. Maffray and Morel, and Bruce, Hoang and Sawada, have proved that 3-colorability of P5-free graphs has a finite forbidden induced subgraphs characterization, while Hoang, Moore, Recoskie, Sawada, and Vatshelle have shown that k-colorability of P5-free graphs for k≥4 does not. These authors have also shown, aided by a computer search, that 4-colorability of (P5,C5)-free graphs does have a finite forbidden induced subgraph characterization. We prove that for any k, the k-colorability of (P6,C4)-free graphs has a finite forbidden induced subgraph characterization. We provide the full lists of forbidden induced subgraphs for k=3 and k=4. As an application, we obtain certifying polynomial time algorithms for 3-coloring and 4-coloring (P6,C4)-free graphs. (Polynomial time algorithms have been previously obtained by Golovach, Paulusma, and Song, but those algorithms are not certifying); To complement these results we show that in most other cases the k-coloring problem for (Pt,Cℓ)-free graphs is NP-complete. Specifically, for ℓ=5 we show that k-coloring is NP-complete for (Pt,C5)-free graphs when k≥4 and t≥7; for ℓ≥6 we show that k-coloring is NP-complete for (Pt,Cℓ)-free graphs when k≥5, t≥6; and additionally, for ℓ=7, we show that k-coloring is also NP-complete for (Pt,C7)-free graphs if k=4 and t≥9. This is the first systematic study of the complexity of the k-coloring problem for (Pt,Cℓ)-free graphs. We almost completely classify the complexity for the cases when k≥4,ℓ≥4, and identify the last three open cases.
A graph is H-free if it does not contain an induced subgraph isomorphic to H. We denote by Pk and Ck the path and the cycle on k vertices, respectively. In this paper, we prove that 4-COLORING is NP-complete for P7-free graphs, and that 5-COLORING is NP-complete for P6-free graphs. These two results improve all previous results on k-coloring Pt-free graphs, and almost complete the classification of complexity of k-COLORING Pt-free graphs for k≥4 and t≥1, leaving as the only missing case 4-COLORING P6-free graphs. We expect that 4-COLORING is polynomial time solvable for P6-free graphs; in support of this, we describe a polynomial time algorithm for 4-COLORING P6-free graphs which are also P-free, where P is the graph obtained from C4 by adding a new vertex and making it adjacent to exactly one vertex on the C4.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.