Cover numbers by certain graph families
Márton Marits · 2024
Read Cover numbers by certain graph families by Márton Marits (2024) 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-2412-08980.txt.
Introduction
Márton Marits asks how many simple graphs it takes to cover a complicated one in this 2024 mathematics paper. The cover number counts the fewest graphs from a chosen family whose edges together make the target graph. The idea echoes a classic paper on graph covers.
For families defined by a rule linking colors needed to cliques present, he finds an exact formula that works for any non-decreasing rule. He then lines up five families in a chain, from the strictest equality of color and clique counts through perfect graphs and two split-like families to plain bipartite graphs. At every step of the chain the gap between cover numbers can be made as large as one likes. Finally he shows the cover number by unipolar graphs escapes any formula in the two classic counts. The results map where covering stays tame and where it runs wild.
Catalog record
| CREATOR | Márton Marits |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 17 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-08980
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Cover numbers by certain graph families Márton Marits Abstract We define the cover number of a graph G G by a graph class 𝒫 \mathcal{P} as the minimum number of graphs of class 𝒫 \mathcal{P} required to cover the edge set of G G . Taking inspiration from a paper by Harary, Hsu and Miller [ 5 ] , we find an exact formula for the cover number by the graph classes { G ∣ χ ( G ) ≤ f ( ω ( G ) ) } \{G\mid\chi(G)\leq f(\omega(G))\} for all non-decreasing functions f f . After this, we establish a chain of inequalities with five cover numbers, the one by the class { G ∣ χ ( G ) = ω ( G ) } \{G\mid\chi(G)=\omega(G)\} , by the class of perfect graphs, generalized split graphs, co-unipolar graphs and finally by bipartite graphs. We prove that at each inequality, the difference between the two sides can grow arbitrarily large. We also prove that the cover number by unipolar graphs cannot be expressed in terms of the chromatic or the clique number. Keywords : Graph covering, chromatic number, clique number, chi-bounded graph families. 1 Introduction Let \mathcal{P} be a class of graphs. A covering of a graph G by graphs of class \mathcal{P} is an expression E(G)=E(G_{1})\cup\dots\cup E(G_{k}) of the edges of G as the union of the edge sets of the graphs G_{1},\dots G_{k} , such that for all i\in\{1,\dots,k\} , we have G_{i}\in\mathcal{P} . From now, for brevity we will simply write G_{i} in place of E(G_{i}) . Furthermore, unless stated otherwise, all logarithms in this article are taken to the base 2. The smallest number k such that G admits a covering by k graphs of class \mathcal{P} is called the cover number of G by \mathcal{P} . We denote this number by c_{\mathcal{P}}(G) . Cover numbers by various classes have been investigated previously. An early survey of the topic is [ 4 ] . The cover number by bipartite graphs is called biparticity by Harary, Hsu and Miller [ 5 ] , and their paper presents an explicit formula for its value. In Gyárfás, Marits and Tóth [ 3 ] , we have seen an investigation of the cover number by comparability graphs. The cover number where \mathcal{P} is taken to be the class of planar graphs is called thickness and has a rich literature, surveyed in [ 7 ] . The following trivial general result can be obtained for cover numbers. Theorem 1 . Let \mathcal{P} and \mathcal{Q} be two graph classes. Then \mathcal{P}\subseteq\mathcal{Q} if and only if c_{\mathcal{P}}(G)\geq c_{\mathcal{Q}}(G) for all graphs G . Proof. The \implies direction is obvious: if \mathcal{P} is a subset of \mathcal{Q} , then any covering by \mathcal{P} -graphs is also a covering by \mathcal{Q} -graphs. To prove the converse, suppose that c_{\mathcal{P}}(G)\geq c_{\mathcal{Q}}(G) for all graphs G . Then if P\in\mathcal{P} , then obviously c_{\mathcal{P}}(P)=1 . The inequality we assumed therefore implies c_{\mathcal{Q}}(P)=1 , which in turn means that P\in\mathcal{Q} . ∎ The cover number by bipartite graphs is named biparticity by Harary, Hsu and Miller in [ 5 ] , and is shown to be equal to \left\lceil\log_{2}\chi(G)\right\rceil for all graphs G . In this article, we will denote this number by c_{\mathbf{BIP}} . Generalizing their result, it is also possible to find a formula for the cover number by graphs of bounded chromatic numbers. The following result is thus obtained for the class \{G\mid\chi(G)\leq k\} . We will denote the cover number by this class by c_{\{\chi\leq k\}} . Theorem 2 ( [ 5 ] ) . For all graphs G , we have c_{\{\chi\leq k\}}(G)=\left\lceil\frac{\log\chi(G)}{\log k}\right\rceil The theorem and the proof only work for constant k . In this paper, we will show that substituting a function of \omega(G) for k still yields the expected formula. Let f\colon\mathbb{N}\to\mathbb{N} be a function that is non-decreasing, and one that majorizes the identity function. We say that a graph class \mathcal{P} is \chi -bounded with \chi -binding function f if every graph G\in\mathcal{P} has \chi(G)\leq f(\omega(G)) . This concept was introduced by Gyárfás in [ 2 ] , and a survey of the topic can be found in [ 9 ] . Using the idea of the above definition, for any suitable f we can define the graph class \{G\mid\chi(G)\leq f(\omega(G))\} , which we will abbreviate as \{\chi\leq f(\omega)\} . Generalizing 2 , we prove the following statement about the cover number by this class of graphs. Theorem 3 . For all graphs G , we have c_{\{\chi\leq f(\omega)\}}(G)=\left\lceil\frac{\log\chi(G)}{\log f(\omega(G))}\right\rceil In particular, taking f to be the identity function, we get an exact expression for the covering number by graphs G with \chi(G)=\omega(G) . Corollary 4 . For all graphs G , we have c_{\{\chi=\omega\}}(G)=\left\lceil\frac{\log\chi(G)}{\log\omega(G)}\right\rceil Taking f in Theorem 3 to be a constant function formally gives back Theorem 2 . Our result is therefore an extension of this previously-known theorem. Obviously, a graph class \mathcal{P} is chi-bounded with chi-binding function f if and only if \mathcal{P}\subseteq\{\chi\leq f(\omega)\} . Using the trivial Theorem 1 and the new Theorem 3 , we can give an equivalent condition for chi-boundedness. Corollary 5 . The graph class \mathcal{P} is chi-bounded with chi-binding function f if and only if c_{\mathcal{P}}(G)\geq\left\lceil\frac{\log\chi(G)}{\log f(\omega(G))}\right\rceil for all graphs G . A graph G is called perfect if G all of its induced subgraphs are in the class \{\chi=\omega\} . This class of graphs has garnered considerable interest, much more than the class \{\chi=\omega\} that we found results about. We will denote the cover number by perfect graphs by c_{\mathbf{PERF}} . A unipolar graph is a graph G such that V(G)=V(A)\dot{\cup}V(B) such that A is a clique and B is the disjoint union of cliques. A graph is called co-unipolar if its complement is unipolar. Furthermore, a graph is called generalized split (GSP) if it is either unipolar or co-unipolar. Generalized split graphs make up “almost all” perfect graphs, according to a result of Prömel and Steger [ 8 ] and the Strong Perfect Graph theorem [ 1 ] . We will denote the cover number by unipolar graphs by c_{\mathbf{UNIP}} , the cover number by co-unipolar graphs as c_{\mathbf{coUNIP}} and the cover number by GSP graphs as c_{\mathbf{GSP}} . With all these cover numbers defined, we can repeatedly use Theorem 1 to establish the following chain of inequalities. In order to make the equations look cleaner, we take each cover number, as well as the chromatic and clique numbers as functions acting on graphs. Between functions, the inequalities are defined pointwise. Theorem 6 . Taking each cover number, as well as the clique number and the chromatic number as functions acting on graphs, the following holds: \left\lceil\frac{\log\chi}{\log\omega}\right\rceil=c_{\{\chi=\omega\}}\leq c_{\mathbf{PERF}}\leq c_{\mathbf{GSP}}\leq c_{\mathbf{coUNIP}}\leq c_{\mathbf{BIP}}=\left\lceil\log\chi\right\rceil For the cover numbers in the middle, we have found no explicit formula in terms of the chromatic number and the clique number. We can however establish that at every inequality, the difference between the two cover numbers can get arbitrarily large. This is despite the close relationship between the graph classes in question. For example, “almost all” perfect graphs are GSP [ 8 ] , but there are