
arXiv: 1704.06667
AbstractA graph G is said to be 2‐divisible if for all (nonempty) induced subgraphs H of G, can be partitioned into two sets such that and . (Here denotes the clique number of G, the number of vertices in a largest clique of G). A graph G is said to be perfectly divisible if for all induced subgraphs H of G, can be partitioned into two sets such that is perfect and . We prove that if a graph is ‐free, then it is 2‐divisible. We also prove that if a graph is bull‐free and either odd‐hole‐free or P5‐free, then it is perfectly divisible.
Coloring of graphs and hypergraphs, 05C15, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), perfect divisibility, graph coloring, FOS: Mathematics, 2-divisibility, Mathematics - Combinatorics, Combinatorics (math.CO)
Coloring of graphs and hypergraphs, 05C15, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), perfect divisibility, graph coloring, FOS: Mathematics, 2-divisibility, Mathematics - Combinatorics, Combinatorics (math.CO)
| 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). | 31 | |
| 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. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
