Timeline for Is there a term for this graph subset?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 22, 2017 at 0:16 | comment | added | Daniel Soltész | @DominicvanderZypen Take a graph $H$ on n vertices that is $k$-colorable. Add $\binom{n}{k-1}$ extra vertices and join these to the $(k-1)$ sets of $H$. Then the resulting graph is still $k$-colorable, and the additional set of vertices is independent (or stable) satisfies the required property. | |
| Jun 21, 2017 at 17:32 | comment | added | JonCC | @DominicvanderZypen Furthermore, it can be shown that for any positive integer $k$ and any graph $H$ of order $k$, there exists a graph $G$ with a $k$-rainbow set $S$ (so $\chi(G)=k$) such that the subgraph of $G$ induced by $S$ is [isomorphic to] $H$. | |
| Jun 21, 2017 at 16:05 | comment | added | Joel David Hamkins | @DominicvanderZypen It seems to me that you can make examples where $S$ is discrete---no edges at all and hence 1-colorable---but still must have $k$ colors when the whole of $G$ is $k$-colored, because of how $S$ relates to the other nodes of $G$, which are not in $S$. To give a simple example, consider a 6-cycle, which has chromatic number 2, and let $S$ be the nodes 1 and 4. So $S$ is discrete, but any coloring of the 6-cycle will place two different colors on the nodes of $S$. I'm sure you can make more extreme examples. | |
| Jun 21, 2017 at 15:38 | comment | added | Dominic van der Zypen | @JoelDavidHamkins What is an example of a subset $S$ that has the property described in the question, but $\chi(S)<k$ when $S$ is considered as an induced subgraph? Can $\chi(S)$ become arbitrarily small with respect to $k$? | |
| Jun 19, 2017 at 9:00 | comment | added | monkeymaths | Such a set is a 'transversal' of every partition of the vertex-set into independent sets, so I'd maybe call it a 'chromatic transversal'. You might also say that it intersects every independent set $X$ for which $G - X$ is $(k-1)$-colourable. | |
| Jun 16, 2017 at 19:06 | comment | added | JonCC | Thank you for all of your comments so far. I have made an edit to address the matter of $k$ being equal to $\chi(G)$. I hope this explains why I originally phrased "rainbow sets" in terms of $k$ rather than $\chi$. | |
| Jun 16, 2017 at 19:03 | history | edited | JonCC | CC BY-SA 3.0 |
added 456 characters in body
|
| Jun 16, 2017 at 18:49 | comment | added | Daniel Soltész | I think this is only interesting if $k= \chi(G)$ otherwise only the whole vertex set has this property. I'd use something like $\chi$-witness set or $\chi$-intersecting set (it intersects every color class) or always $\chi$-colored set (maybe ACC set as an abbreviation). | |
| Jun 16, 2017 at 18:29 | comment | added | Gerhard Paseman | How about 'witness for chromatic number'? Gerhard "Gives It A CS Flavor" Paseman, 2017.06.16. | |
| Jun 16, 2017 at 18:25 | comment | added | Joel David Hamkins | Since $S$ may not have chromatic number $k$ by itself, it would be good to use terminology that doesn't suggest that it does. | |
| Jun 16, 2017 at 18:20 | history | edited | JonCC |
edited tags
|
|
| Jun 16, 2017 at 14:51 | comment | added | Timothy Chow | Perhaps something like "$k$-chromatic core" is a possibility, although "core" is unfortunately also already used in graph theory. | |
| Jun 16, 2017 at 13:35 | comment | added | Tom De Medts | I like "$k$-rainbow" better than "non-($k-1$)-extendible" :) Perhaps a variation on this theme such as "$k$-prismatic" or "$k$-polychromatic" might be a good name? | |
| Jun 16, 2017 at 8:03 | comment | added | Jon Noel | Hmm I do not know of any standard terminology for such a set, but it seems to be a natural concept. The property that you are describing is equivalent to saying that there does not exist a $(k-1)$-colouring of $S$ which extends to a proper colouring of $G$. So, perhaps a name like "non-$(k-1)$-extendible" would be appropriate. | |
| Jun 15, 2017 at 23:55 | review | First posts | |||
| Jun 16, 2017 at 3:15 | |||||
| Jun 15, 2017 at 23:52 | history | asked | JonCC | CC BY-SA 3.0 |