On graphs without four-vertex induced subgraphs
Kathie Cameron 1, Chính T. Hoàng 2, Taite LaGrange 3 · 2025
Read On graphs without four-vertex induced subgraphs by Kathie Cameron 1, Chính T. Hoàng 2, Taite LaGrange 3 (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-2505-00202.txt.
Introduction
Kathie Cameron, Chinh Hoang, and Taite LaGrange solve a graph coloring problem in a 2025 mathematics paper. Coloring assigns labels to graph points so that linked points differ, and the difficulty of coloring certain graph families is a known open question. The authors focus on graphs that avoid several small patterns as contained subgraphs.
For one such family, they design an algorithm that colors any member graph in polynomial time. The algorithm rests on a structural theorem that describes what these graphs must look like. That structure breaks the graph into parts that are easy to color and combine. The result settles coloring for this subclass, while the broader problem for the parent family remains open.
Catalog record
| CREATOR | Kathie Cameron 1, Chính T. Hoàng 2, Taite LaGrange 3 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 350 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-00202
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On graphs without four-vertex induced subgraphs Kathie Cameron 1, Chính T. Hoàng 2, Taite LaGrange 3 Abstract Given a family F F of graphs, a graph G G is F F -free if it does not contain any graph in F F as an induced subgraph. The problem of determining the complexity of colouring ( c l a w claw , 4 K 1 4K_{1} )-free graphs is a well-known open problem. In this paper we solve the colouring problem for a subclass of ( c l a w claw , 4 K 1 4K_{1} )-free graphs. We design a polynomial-time algorithm to colour ( c l a w claw , 4 K 1 4K_{1} , b r i d g e bridge , C 4 C_{4} -twin)-free graphs. This algorithm is derived from a structural theorem on ( c l a w claw , 4 K 1 4K_{1} , b r i d g e bridge , C 4 C_{4} -twin)-free graphs. Keywords : Graph colouring, line-graph, c l a w claw , b r i d g e bridge , C 4 C_{4} -twin, clique-width 1 Department of Mathematics, Wilfrid Laurier University, Waterloo, Ontario, Canada 2 Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo, Ontario, Canada 3 David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada 1 Introduction Vertex colouring is the problem of assigning a minimum number of colours to the vertices of a graph G so that no two adjacent vertices receive the same colour. Vertex colouring is NP-hard for general graphs. The problem is even NP-hard for some well-studied restricted classes of graphs such as claw -free graphs (definitions not given here will be given later). However vertex colouring can be solved in polynomial time for many well-known classes of graph such as perfect graphs. Let L be a set of graphs. A graph G is L -free if G does not contain any graph of L as an induced subgraph. There has been keen interest in graphs whose forbidden list L contains graphs with four vertices, and a recent paper of Lozin and Malyshev [ 16 ] discusses the state of the art on this problem, identifying three outstanding classes: L=(claw,4K_{1}),L=(claw,4K1,co-diamond) , and L=(4K_{1},C_{4}) . To be more formal, if L is a set of four-vertex graphs, then it is known that vertex colouring L -free graphs is polynomial-time solvable or NP-hard except when L is one of the above three classes. We are interested in the class L=(claw,4K_{1}) . ( 4K_{1} is the stable set on four vertices.) Given a graph G , the line-graph L(G) of G is defined to be the graph whose vertices are the edges of G , and two vertices of L(G) are adjacent if their corresponding edges in G are incident. Beineke [ 2 ] derived a characterization of line-graphs in terms of a set of nine forbidden induced subgraphs (see Figure 1 ), two of which are the claw and K_{5}-e . Fraser, Hamel, Hoàng and Maffray [ 12 ] showed that vertex colouring can be solved in polynomial time for (claw,4K_{1},K_{5}-e) -free graphs. Given the connection between (claw,4K_{1}) -free graphs and (4K_{1}) -free line-graphs, it is natural to ask about polynomial-time solvability of vertex colouring of graphs where K_{5}-e is replaced by one of the other nine forbidden induced subgraphs. Three of the graphs in Beineke’s list contain a K_{4} (a clique on four vertices). They are K_{5}-e , co- R , and bridge . The following problem then might be of interest: Is there a polynomial-time algorithm for vertex colouring (claw,4K_{1},F) -free graphs, where F is the graph co- R or the bridge ? Abuadas and Hoàng [ 1 ] positively solved the above problem for F = co- R . In this paper, we investigate the question for the bridge . We are not able to fully answer the question for the bridge . However, we are able to provide the answer if we add the C_{4} -twin to the list of forbidden subgraphs. Note that C_{4} -twin is one of the nine forbidden induced subgraphs for line-graphs. Furthermore, C_{4} -twin-free graphs do not contain complements of chordless cycles with at least seven vertices. In fact, C_{4} -twin is the only graph of the nine forbbiden induced subgraphs with this property. This fact allows us to use known perfect graph algorithms to establish our main result. Theorem 1.1 There is a polynomial-time algorithm to colour a ( claw , 4K_{1} , bridge , C_{4} -twin)-free graph. The purpose of this paper is to prove Theorem 1.1 . Our results have connections to perfect graphs and clique-width. As we will see later, the theorem below implies Theorem 1.1 . Theorem 1.2 Let G be a ( claw , 4K_{1} , bridge , C_{4} -twin)-free graph. Then one of the following holds. (i) G is perfect. (ii) G has bounded clique-width. • • • • Claw • • • • • • P_{5} -Twin • • • • • • co- R • • • • • C_{4} -twin • • • • • • C_{5} -twin • • • • • • bridge • • • • • • 5-wheel • • • • • • co- A • • • • • K_{5}-e Figure 1 : The nine forbidden sugraphs for line-graphs In Section 2 , we discuss background results related to our work and establish a number of new results on clique-width. In Sections 3 - 7 , we study the structure of ( claw , 4K_{1} , bridge , C_{4} -twin)-free graphs. In Section 8 , we prove Theorems 1.1 and 1.2 . Finally, in Section 9 , we discuss open problems related to our work. 2 Definitions and Background In this section, we discuss the background results needed to prove our main theorem. This section has two subsections. In the first subsection, we discuss claw -free graphs. In the second subsection, we discuss clique-width of graphs. 2.1 Claw-free graphs Let \chi(G) denote the chromatic number of G (the minimum number of colours for which a graph can be coloured), and \omega(G) denote the number of vertices in a largest clique of G . A hole is an induced cycle on at least four vertices. An antihole is the complement of a hole. A k -hole is a hole with k vertices. Our results rely on known theorems on perfect claw -free graphs, and we discuss these results now. A graph G is perfect if for each induced subgraph H of G , we have \chi(H)=\omega(H) . A graph is Berge if it does not contain an odd hole or odd antihole as an induced subgraph. Parthasarathy and Ravindra [ 17 ] proved that claw -free Berge graphs are perfect. Chvátal and Sbihi [ 7 ] showed that claw -free perfect graphs can be recognized in polynomial time. Hsu [ 15 ] showed that these graphs can be coloured in polynomial