
arXiv: 1702.00622
A hereditary class $\mathcal{G}$ of graphs is $��$-bounded if there is a $��$-binding function, say $f$ such that $��(G) \leq f(��(G))$, for every $G \in \cal{G}$, where $��(G)$ ($��(G)$) denote the chromatic (clique) number of $G$. It is known that for every $2K_2$-free graph $G$, $��(G) \leq \binom{��(G)+1}{2}$, and the class of ($2K_2, 3K_1$)-free graphs does not admit a linear $��$-binding function. In this paper, we are interested in classes of $2K_2$-free graphs that admit a linear $��$-binding function. We show that the class of ($2K_2, H$)-free graphs, where $H\in \{K_1+P_4, K_1+C_4, \overline{P_2\cup P_3}, HVN, K_5-e, K_5\}$ admits a linear $��$-binding function. Also, we show that some superclasses of $2K_2$-free graphs are $��$-bounded.
Revised version
FOS: Computer and information sciences, Coloring of graphs and hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Discrete Mathematics (cs.DM), chromatic number, graph classes, FOS: Mathematics, Mathematics - Combinatorics, Structural characterization of families of graphs, \(2 K_2\)-free graphs, Combinatorics (math.CO), clique number, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Coloring of graphs and hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Discrete Mathematics (cs.DM), chromatic number, graph classes, FOS: Mathematics, Mathematics - Combinatorics, Structural characterization of families of graphs, \(2 K_2\)-free graphs, Combinatorics (math.CO), clique number, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
