1 Introduction
All graphs in this paper are finite and simple. We say that a graph contains a graph if is isomorphic to an induced subgraph of . A graph is free if it does not contain . For a family of graphs, is free if is free for every . When consists of two graphs, we write free instead of free. As usual, and denote the path on vertices and the cycle on vertices, respectively. The complete graph on vertices is denoted by . The graph is also referred to as the triangle. Let the diamond be the graph obtained from by removing an edge. For two graphs and , we use to denote the disjoint union of and . For a positive integer , we use to denote the disjoint union of copies of . The complement of is denoted by . A clique (resp. stable set) in a graph is a set of pairwise adjacent (resp. nonadjacent) vertices. A colouring of a graph is a function such that whenever and are adjacent in . Equivalently, a colouring of is a partition of into stable sets. A graph is colourable if it admits a colouring. The chromatic number of a graph , denoted by , is the minimum number for which is colourable. The clique number of , denoted by , is the size of a largest clique in . Obviously, for any graph .
A family of graphs is said to be bounded if there exists a function such that for every graph , every induced subgraph of satisfies . The function is called a binding function for . The notion of bounded families was introduced by Gyárfás [11] in 1987. Since then it has received considerable attention for free graphs.
We briefly review some results in this area. A hole in a graph is an induced cycle of length at least 4. An antihole is the complement of a hole. A hole or antihole is odd or even
if it is of odd or even length, respectively. The famous Strong Perfect Graph Theorem
[6] says that the class of graphs without odd holes or odd antiholes is bounded and the binding function is the identity function . If we only forbid odd holes, then the resulting class remains bounded but the best known binding function is double exponential [17]. On the other hand, if even holes are forbidden, then a linear binding function exists [1]: every evenholefree graph satisfies . In recent years, there has been an ongoing project led by Scott and Seymour that aims to determine the existence of binding functions for classes of graphs without holes of various lengths. We refer the reader to the recent survey by Scott and Seymour [18] for various nice results. One thing to note is that most binding functions in this setting are exponential.Another line of research is the study of free graphs for a fixed graph . A classsical result of Erdős [8] shows that the class of free graphs is not bounded if contains a cycle. Gyárfás [10] conjectured that the converse is also true (known as the Gyárfás Conjecture), and proved the conjecture when [11]: every free graph has . Similar to results in [18], this binding function is exponential in . It is natural to ask the following question.
Is it possible to improve the exponential bound for free graphs to a polynomial bound?
This turns out to be a very difficult question, and not much progress has been made over the past 30 years. It remains open whenever . (For , free graphs are perfect and hence is the binding function.) Therefore, researchers have started to investigate subclasses of free graphs, hoping to discover techniques and methods that would be useful for tackling the problem. A natural type of subclass is to forbid a second graph in addition to forbidding . For example, it was shown by Gaspers and Huang [9] that every free graph has . This 3/2 bound was improved recently by Karthick and Maffray [13] to the optimal bound 5/4: every free graph has . In another work, Karthick and Maffray [14] showed that every (, diamond)free graph satisfies . Bharathi and Choudum [2] gave a cubic binding function for the class of (, diamond)free graphs. For the class of (, diamond)free graphs, a common superclass of (, diamond)free graphs and (, diamond)free graphs, Karthick and Mishra [15] proved that is a binding function, greatly improving the result for (, diamond)free graphs. In the same paper, they also obtained an optimal bound for (, diamond)free graphs when the clique number is 3: every (, diamond, )free graph is 6colourable. For more results of this flavor, see [4, 5, 12, 19].
Our Contributions
In this paper, we give an optimal bound for the class of (, diamond)free graphs. We prove that each (, diamond)free graph satisfies (Theorem 3 in Section 4). The bound is tight since it is attained by the complement of the famous 27vertex Schläfli graph [15]. Our result unifies the results on the existence of linear binding functions for the class of (, diamond)free graphs [14], (, diamond)free graphs [2], and (, diamond)free graphs [15], and answers an open question in [15].
2 Preliminaries
For general graph theory notation we follow [3]. Let be a graph. The neighbourhood of a vertex , denoted by , is the set of vertices adjacent to . For a set , let and . The degree of , denoted by , is equal to . For and , we denote by the set of neighbours of that are in , i.e., . For , we say that is complete (resp. anticomplete) to if every vertex in is adjacent (resp. nonadjacent) to every vertex in . For and , we say is complete (resp. anticomplete) to if is adjacent (resp. nonadjacent) to every vertex in . A vertex subset is a clique cutset if has more components than and induces a clique. For , the subgraph induced by is denoted by . We shall often write for if the context is clear. We say that a vertex distinguishes and if is adjacent to exactly one of and . A component of a graph is trivial if it has only one vertex, and nontrivial otherwise.
A graph is perfect if for each induced subgraph of . An imperfect graph is a graph that is not perfect. One of the most celebrated theorems in graph theory is the Strong Perfect Graph Theorem [6].
Theorem 1 ([6]).
A graph is perfect if and only if it does not contain an odd hole or an odd antihole as an induced subgraph.
Another useful result is a characterization of 3colourable free graphs.
3 Structure of Imperfect (, diamond)Free Graphs
In this section we study the structure of imperfect (, diamond)free graphs. It follows from Theorem 1 that every imperfect (, diamond)free graph contains an induced . Let be an imperfect (, diamond)free graph and let induce a in with edges for . Note that all indices are modulo 5. We partition into the following subsets:
Let , , , and . Since is diamondfree, it follows that and thus . We now prove a number of useful properties about those subsets.

Each component of is a clique.
This follows directly from the fact that is diamondfree.

The sets and are anticomplete.
If and are adjacent, then induces a .

The sets and are complete.
If and are not adjacent, then induces a , a contradiction.

Each is a clique.
If are not adjacent, then induces a diamond.

The set for some .
We show that for each either or is empty. Suppose not. Let and . Then either induces a or induces a diamond, depending on whether and are adjacent. Therefore, the property holds.

The set is anticomplete to .
By symmetry, it suffices to show that is anticomplete to . If and are adjacent, then induces a diamond.

The set is complete to .
By symmetry, it suffices to show that is complete to . If and are not adjacent, then induces a .

Each is a stable set.
If are adjacent, then induces a diamond.

Each vertex in is either complete or anticomplete to each component of and .
If is adjacent to () but not adjacent to () with , then () induces a diamond.

Each vertex in has at most one neighbour in each component of , and .
Suppose that a vertex has two neighbours and in the same component of where and . Since each component of is a clique by a, . Then induces a diamond in .

Each vertex in is anticomplete to each nontrivial component of .
Suppose that has a neighbour in a nontrivial component of . Let be a vertex in that component other than . By j, we have that . Then induces a .

The set is anticomplete to if . Moreover each vertex in has at most one neighbour in .
Suppose that is adjacent to some for some . Since and have exactly one common neighbour in , it follows that induces a diamond. This proves the first part of the claim. Suppose that is adjacent to two vertices . By d, . Then induces a diamond.

Each has at most one vertex. Moreover, is a stable set.
If contains two vertices and , then either or induces a diamond, depending on whether . This proves the first part of the claim. Let and with . Note that there exists an index such that is a common neighbour of and and is adjacent to exactly one of and . If , then induces a diamond.

The set is anticomplete to .
By symmetry, it suffices to show that is anticomplete to . If is adjacent to , then induces a diamond.

Each vertex in is either complete or anticomplete to each component of .
If is adjacent to but not to with , then induces a diamond.

Each vertex in has at most one neighbour in each component of and .
If has two neighbours and in the same component of (), then () induces a diamond.

The set is anticomplete to if and complete to if .
If is not adjacent to , then induces a diamond. This proves the second part of the claim. Note that and have exactly one common neighbour in , say . If , then or induces a diamond.

The set is anticomplete to if .
Let . Note that if , then each vertex is adjacent to exactly one of and . If , then induces a diamond.

If is not stable, then .

If is not empty, then each of and contains at most one vertex.

The set is anticomplete to .
Suppose that has a neighbour . By symmetry, we may assume that is adjacent to but adjacent to none of , and . Then induces a .
4 The Optimal Bound
In this section, we derive an optimal bound for (, diamond)free graphs. An atom is a graph without clique cutsets. Two nonadjacent vertices and in a graph are comparable if or . The following is the main result of this paper.
Theorem 3.
Let be a (, diamond)free graph. Then .
Proof.
We prove this by induction on . If is disconnected, then we are done by applying the inductive hypothesis to each connected component of . If contains a clique cutset such that is the disjoint union of two subgraphs and , then it follows from the inductive hypothesis that . If contains two nonadjacent vertices and such that , then and , and we are done by applying the inductive hypothesis to . Therefore, we can assume that is a connected atom with no pair of comparable vertices. If is perfect, then by Theorem 1. Otherwise the theorem follows from Theorem 4 below. ∎
Theorem 4.
Let be a connected atom with no pair of comparable vertices. If is (, diamond)free and imperfect, then .
The remainder of the section is devoted to the proof of Theorem 4. We begin with a simple lemma that will be useful later. A matching in a graph is a set of edges such that no two edges in the set meet a common vertex.
Lemma 1.
Let be a graph that can be partitioned into two cliques and such that the edges between and form a matching. If for some integer , then is colourable.
Proof.
Note that either or is a maximum clique of unless and are singletons in which case the maximum size of a clique of is at most 2. Moreover, is perfect by Theorem 1. Since and , it follows that is colourable. ∎
Proof of Theorem 4.
Let be a graph satisfying the assumptions of the theorem. Since is imperfect, it contains an induced , say (in order). We partition as in Section 3. Let . If , then the theorem follows from a known result that every (, diamond)free graph without a is 6colourable [15]. Therefore, we can assume that . The idea is to colour , , and independently using as few colours as possible. However, to obtain the optimal bound, we need to reuse colours in some smart way. In particular, we show that we can reuse one colour from on some , so that the remaining of can be coloured with only 3 colours (Claim 2 and Claim 4). The proof of Claim 4 relies on a computer search combined with a wellknown result characterizing 3colourable free graphs (Theorem 2). See Figure 2 for a diagram illustrating our colouring of with colours.
We first deal with the components of .
Claim 1.
Each component of is colourable.
Proof.
Let be an arbitrary component of . Suppose first that has a neighbour in for some . If is adjacent to but not to with , then induces a . So, is complete to . Since is diamondfree, is a clique of size at most . Thus, is colourable.
Suppose now that has no neighbour in . It follows from u that is anticomplete to . Since is connected, has a neighbour . Let and for . Since is connected, . Suppose that contains a vertex for some . By definition, there is an induced path such that for each . Then for some , we have that contains an induced , where and . This shows that . Since is diamondfree, each component of is free and thus is a clique. Since is free, each vertex in is either complete or anticomplete to each component of . Moreover, if a component of has two neighbours in a component of , then two such neighbours, a vertex in and induce a diamond.
First, we claim that is stable. Suppose not. Let be a component of with at least two vertices and . By definition, has a neighbour in some component of . If has a neighbour with , then is in a component other than , and so induces a diamond. So, is the only neighbour of in . Since has no clique cutset, has a neighbour . Note that there is an induced path where . If distinguishes an edge in , then induces a . So, is complete to . If , then induces a diamond. So, . Note that the above argument works for each neighbour of in . Hence, if there is another neighbour of , then by m and so induces a diamond. This shows that is a clique cutset that separates from , a contradiction. This proves that is stable.
Secondly, we claim that if , then each component of has size at most 2. Let . If has no neighbour in , then . This contradicts the assumption that has no pair of comparable vertices. So has a neighbour . Note that there is an induced path where . For each nonneighbour of , we have that induces a unless . This shows that is adjacent to each nonneighbour of in . Since has at most one neighbour in each component of , if a component of has size at least 3, then is adjacent to at least two vertices in that component, and so these two vertices, and induce a diamond. This proves the claim.
We now complete the proof using the above two claims. If , then is a clique of size at most , and so is colourable. If , then is 3colourable by the two claims. Since , it follows that is colourable. ∎
Next we deal with for some .
Claim 2.
There exists an index such that can be coloured with colours such that is monochromatic.
Proof.
By e, we may assume that . We consider several cases. In each case we give a desired colouring explicitly. In the following, when we say that we colour a set with a certain colour, we mean that we colour each vertex in the set with that colour. For convenience, we always colour with colour below.
Case 1. is not stable.
By s, we have that . Moreover, is anticomplete to by b, and and are complete to each other by c. By s, if is not stable, then is empty. This implies that one of and is stable. By symmetry, we may assume that is stable. We now colour as follows.
Colour with colours 1, 2, 1, 2, 3 in order.
Colour with colour 2.
Colour each component of with colours in using the smallest colour available.
Colour each component of with colours in using the smallest colour available.
Colour with colour .
We now show that this is a colouring of . Observe first that each trivial component of is coloured with 2 and each trivial component of is coloured with 1. By a, the colouring is proper on . It remains to show that the colour of does not conflict with those colours of . By k, no vertex in can have a neighbour in a nontrivial component of . So, does not conflict with . Suppose that there exists a vertex with colour who has a neighbour . Let be the component of containing . Then is complete to by i. This implies that is a clique and so . This contradicts that is coloured with colour . So, does not conflict with . This proves that the colouring is a proper colouring.
Case 2. is stable but not empty.
By s, we have that and are stable. By t, each of and contains at most one vertex. Let and be the possible vertex in and , respectively. By s, we have that one of and is stable. By symmetry, we may assume that is stable. If is stable, then it is easy to verify that the following is a 3colouring of : , , . Since , one can extend this colouring to a colouring of for any . We now assume that is not stable. By s, we have that . We can colour as follows.
Colour with colours 1, 2, 3, 1, 3 in order.
Colour and with colours 3 and 1, respectively.
Colour each component of with colours in using the smallest colour available.
Colour and with colours 1 and 2, respectively.
Colour with colour .
An argument similar to that in Case 1 shows that this is indeed an colouring of .
Case 3. is empty. We further consider two subcases.
Case 3.1. is not stable.
Suppose first that not empty. Then has at most one vertex. Let be the possible vertex in . Consider the following colouring of .
Colour with colours 1, 2, 3, 1, 3 in order.
Colour each component of with colours in using the smallest colour available.
Colour each component of with colours in using the smallest colour available.
Colour with 2 if exists, and colour vertices in with colours in .
Colour with colour .
By d, we have that . By l, we have that and are anticomplete. By k, we have that is anticomplete to each nontrivial component of . If exists, then is stable by t. It then follows from the definition that each vertex in is coloured with 1. One can easily verify that the above is a proper colouring of . If does not exist, then an argument similar to that in Case 1 shows that this is a proper colouring of .
Suppose now that is empty. Since is diamondfree, the edges between and form a matching. For the same reason, the edges between and each component of form a matching. Consider the following colouring of .
Colour with colours 3, , 1, , 1 in order.
For each component of , pick an arbitrary vertex in the component and colour it with 1. By Lemma 1, there exists a colouring of using colours .
By Lemma 1, there exists a colouring of using colours .
Colour with colour .
Since and are anticomplete, the above colouring (by permuting colours in ) gives an colouring of .
Case 3.2. is stable. By symmetry, is stable.
Suppose first that is not stable. By s, we have that . If is stable, one can easily verify that the following is an colouring of .
Colour with colours 1, 2, , 3, 2 in order.
Colour and with 1 and 2, respectively, and colour each component of with colours in .
Colour vertices in with colours in .
Colour with colour .
If is not stable, then by s. One can obtain a desired colouring as in Case 1.
Now suppose that is stable. By symmetry, is stable. So, each is stable for . We first claim that if both and are not empty, then each of and contains at most one vertex. Let and . By c, it follows that . If is not adjacent to , then induces a . So, is complete to . Then contains at most one vertex, for otherwise two vertices in , and induce a diamond. Similarly, contains at most one vertex. This proves the claim. Now if and are not empty, then since , the following is an colouring of : , , , and . So, we can assume by symmetry that . By t, either or has at most one vertex. One can easily verify that the following is an colouring of .
Colour with colours 3, 1, 2, 1, 2 in order.
Colour and with 2 and 1, respectively, and colour with 3 if .
By Lemma 1, there exists a colouring of using colours in . If contains at most one vertex , we may assume that is coloured with colour .
Colour with colour . ∎
Finally, we deal with .
Claim 3.
The subgraph is trianglefree.
Proof.
Suppose, by contradiction, that contains a triangle with vertices for
Comments
There are no comments yet.