Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Publication
Articles 1 - 2 of 2
Full-Text Articles in Mathematics
Strong Chromatic Index Of Subset Graphs, Jennifer Quinn, Arthur Benjamin
Strong Chromatic Index Of Subset Graphs, Jennifer Quinn, Arthur Benjamin
Jennifer J. Quinn
The strong chromatic index of a graph G, denoted sq(G), is the minimum number of parts needed to partition the edges of G into induced matchings. For 0 ≤ k ≤ l ≤ m, the subset graph Sm(k, l) is a bipartite graph whose vertices are the k- and l-subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. We show that sq(Sm(k, l) ) = m choose l-k and that this number satisfies the strong chromatic index conjecture by Brualdi and Quinn for bipartite graphs. Further, …
Highly Connected Monochromatic Subgraphs Of Multicoloured Graphs, H. Liu, R. Morris, N. Prince
Highly Connected Monochromatic Subgraphs Of Multicoloured Graphs, H. Liu, R. Morris, N. Prince
Noah Prince
We consider the following question of Bollobás: given an r-coloring of E(Kn), how large a k-connected subgraph can we find using at most s colors? We provide a partial solution to this problem when s=1 (and n is not too small), showing that when r=2 the answer is n−2k+2, when r=3 the answer is ⌊(n−k)/2⌋+1 or ⌈(n−k)/2⌉+1, and when r−1 is a prime power then the answer lies between n/(r−1)−11(k2−k)r and (n−k+1)/(r−1)+r. The case s≥2 is considered in a subsequent paper (Liu et al.[6]), where we also discuss some of the more glaring open problems relating to this question.