On the structure of (dart, odd hole)-free graphs

Chính T. Hoàng · 2025

Read On the structure of (dart, odd hole)-free graphs by Chính T. Hoàng (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-20422.txt.

Introduction

Hoang studies the structure of graphs that avoid two patterns, a dart and an odd hole, in a 2025 mathematics paper. A hole is a chordless cycle, and the dart is a small five vertex shape. Graphs free of both patterns turn out to be tightly organized.

Any such graph is perfect, or lacks a stable set of three vertices, or splits as a join or co join of two smaller graphs. That structure yields a fast algorithm for optimal coloring of these graphs. Hoang also proves the family is perfectly divisible, a trait that bounds the colors needed by the square of the largest clique size. The work extends a line of research on dart free graphs and their coloring.

Catalog record

CREATORChính T. Hoàng
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-20422

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the structure of (dart, odd hole)-free graphs Chính T. Hoàng Abstract A hole is a chordless cycle with at least four vertices. A hole is odd if it has an odd number of vertices. A dart is a graph which vertices a , b , c , d , e a,b,c,d,e and edges a ​ b , b ​ c , b ​ d , b ​ e , c ​ d , d ​ e ab,bc,bd,be,cd,de . Dart-free graphs have been actively studied in the literature. We prove that a (dart, odd hole)-free graph is perfect, or does not contain a stable set on three vertices, or is the join or co-join of two smaller graphs. Using this structure result, we design a polynomial-time algorithm for finding an optimal colouring of (dart, odd hole)-free graphs. A graph G G is perfectly divisible if every induced subgraph H H of G G contains a set X X of vertices such that X X meets all largest cliques of H H , and X X induces a perfect graph. The chromatic number of a perfectly divisible graph G G is bounded by ω 2 \omega^{2} where ω \omega denotes the number of vertices in a largest clique of G G . We prove that (dart, odd hole)-free graphs are perfectly divisible. Department of Computer Science and Physics Wilfrid Laurier University Waterloo, Ontario, Canada, N2L 3C5 [email protected] 1 Introduction A hole is a chordless cycle with at least four vertices. An antihole is the complement of a hole. A hole is odd if it has an odd number of vertices. A graph is odd-hole-free if it does not contain, as an induced subgraph, an odd hole. Odd-hole-free graphs have been studied in connection with perfect graphs (definitions not given here will be given later.) Chudnovsky, Scott, Seymour, and Spirkl ( [ 6 ] ) designed a polynomial-time algorithm for finding an odd hole if one exists, in a graph. A result of Král , Kratochvíl, Tuza, and Woeginger ( [ 18 ] ) shows that determining the chromatic number of an odd-hole-free graph in NP-complete. A dart is the graph with vertices a,b,c,d,e and edges ab,bc,bd,be,cd,de . Dart-free graphs generalize the well studied class of claw-free graphs. In this paper, we study (dart, odd hole)-free graphs. We prove that a (dart, odd hole)-free graph is perfect, or does not contain a stable set on three vertices, or is the join or co-join of two smaller graphs. We will use this structural result to design a polynomial-time algorithm for finding an optimal coloring of a (dart, odd hole)-free graph. Interesting results have been obtained for dart-free graphs. Karthick, Maffray and Pastor ( [ 16 ] ) designed a polynomial-time algorithm to (optimally) color a ( P_{5} , dart)-free graph. Branstädt and Mosca ( [ 3 ] ) designed a polynomial-time algorithm to find a largest stable set of a (dart, odd hole)-free graph. Critical dart-free graphs were studied by Xia, Jooken, Goedgebeur and Huang ( [ 24 ] ). Sales and Reed ( [ 23 ] ) studied “perfectly contractile” graphs that are dart-free. Chvátal, Fonlupt, Sun and Zemirline ( [ 7 ] ) gave a polynomial-time algorithm to recognize dart-free perfect graphs. A graph G with at least one edge is k -divisible if the vertex-set of each of its induced subgraphs H with at least one edge can be partitioned into k sets, none of which contains a largest clique of H . It is easy to see that the chromatic number of a k -divisible graph is at most k^{\omega-1} . It was conjectured by Hoàng and McDiarmid ( [ 13 ] , [ 14 ] ) that every odd-hole-free graph is 2-divisible. They proved the conjecture for claw-free graphs ( [ 14 ] ). Hoàng ( [ 12 ] ) proved the conjecture for banner-free graphs. Dong, Song and Xu ( [ 8 ] ) proved the conjecture for dart-free graphs. A graph G is perfectly divisible ( [ 12 ] ) if every induced subgraph H of G contains a set X of vertices such that X meets all largest cliques of H , and X induces a perfect graph. The chromatic number of a perfectly divisible graph G is bounded by \omega^{2} where \omega denotes the number of vertices in a largest clique of G . We will prove that (dart, odd hole)-free graphs are perfectly divisible. In Section 2 , we give the definitions used in this paper and discuss background results that we need to establish our results. In Section 3 , we prove that (dart, odd hole)-free graphs are perfectly divisible. We will also give a proof, different from that of [ 8 ] , that (dart, odd hole)-free graphs are 2-divisible. In Section 4 , we give polynomial-time algorithms for finding a minimum coloring of a (dart, odd hole)-free graph. Finally, in Section 5 , we discuss open problems related to our work. 2 Definitions and background The claw , dart and banner are represented in Figure 1 . Let C_{k} denote the cordless cycle on k vertices. Let P_{k} denote the chordless path on k vertices. A hole is the graph C_{k} with k\geq 4 . A hole is odd if it has an odd number of vertices. An antihole is the complement of a hole. A clique on three vertices is called a triangle . For a given graph H , it is customary to let co - H denote the complement of H . Thus, a co-triangle is the complement of the triangle. Let L be a collection of graphs. A graph G is L -free if G does not contain an induced subgraph isomorphic to a graph in L . In particular, a graph is (dart, odd hole)-free if it does not contain an induced subgraph isomorphic to a dart or an odd hole. Let G be a graph. Then \chi(G) denotes the chromatic number of G , and \omega(G) denotes, the clique number of G , that is, the number of vertices in a largest clique of G . The number of vertices in a largest stable set of G is denoted by \alpha(G) . The girth of G is the length of the shortest cycle of G (if a cycle exists). Let v be a vertex of G and X be a subset of V(G) that does not contain v . We say that v is X-complete if v is adjacent to all vertices of X , and v is X-anticomplete if v is non-adjacent to all vertices of X . Let A and B be two disjoint subsets of V(G) . We say that A and B form a join (respectively, co-join ) if there are all (respectively, no) edges between A and B , that is, every vertex x\in A is B -complete (respectively, B -anticomplete). The join of A and B is denoted by A\;\hbox to14.18pt{\vbox to14.18pt{\pgfpicture\makeatletter\hbox{\hskip 7.09111pt\lower-7.09111pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} { {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 9.54 0 C 9.54 5.27 5.27 9.54 0 9.54 C -5.27 9.54 -9.54 5.27 -9.54 0 C -9.54 -5.27 -5.27 -9.54 0 -9.54 C 5.27 -9.54

Read the complete text