New classes of panchromatic digraphs
A digraph D=(V,A) with a k-colouring of its arcs ς:A→[k] is said to have a ς-kernel if there exists a subset K of V such that there are no monochromatic uv-paths for any two vertices u,v∈K, but for every w∈V−K, there exists a vertex v∈K such that there is a monochromatic wv-path in D. The panchromat...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2015-11-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S097286001500033X |
| _version_ | 1828324334704263168 |
|---|---|
| author | Hortensia Galeana-Sánchez Micael Toledo |
| author_facet | Hortensia Galeana-Sánchez Micael Toledo |
| author_sort | Hortensia Galeana-Sánchez |
| collection | DOAJ |
| description | A digraph D=(V,A) with a k-colouring of its arcs ς:A→[k] is said to have a ς-kernel if there exists a subset K of V such that there are no monochromatic uv-paths for any two vertices u,v∈K, but for every w∈V−K, there exists a vertex v∈K such that there is a monochromatic wv-path in D. The panchromatic number, π(D), of D is the greatest integer k for which D has a ς-kernel for every possible k-colouring of its arcs. D is said to be a panchromatic digraph if, for every k≤|A| and every k-colouring ς:A→[k], D has a ς-kernel. In this paper we study the panchromaticity of cycles. In particular, we show that even cycles are panchromatic and that π(C)=2 when C is an odd cycle. We also set sufficient conditions, in terms of its induced subdigraphs, for a digraph D to be panchromatic, and we show through counterexamples that these results cannot be improved. |
| first_indexed | 2024-04-13T19:04:01Z |
| format | Article |
| id | doaj.art-cbad86159d7847ec91c95ee17645348e |
| institution | Directory Open Access Journal |
| issn | 0972-8600 |
| language | English |
| last_indexed | 2024-04-13T19:04:01Z |
| publishDate | 2015-11-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-cbad86159d7847ec91c95ee17645348e2022-12-22T02:34:01ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002015-11-0112212413210.1016/j.akcej.2015.11.006New classes of panchromatic digraphsHortensia Galeana-SánchezMicael ToledoA digraph D=(V,A) with a k-colouring of its arcs ς:A→[k] is said to have a ς-kernel if there exists a subset K of V such that there are no monochromatic uv-paths for any two vertices u,v∈K, but for every w∈V−K, there exists a vertex v∈K such that there is a monochromatic wv-path in D. The panchromatic number, π(D), of D is the greatest integer k for which D has a ς-kernel for every possible k-colouring of its arcs. D is said to be a panchromatic digraph if, for every k≤|A| and every k-colouring ς:A→[k], D has a ς-kernel. In this paper we study the panchromaticity of cycles. In particular, we show that even cycles are panchromatic and that π(C)=2 when C is an odd cycle. We also set sufficient conditions, in terms of its induced subdigraphs, for a digraph D to be panchromatic, and we show through counterexamples that these results cannot be improved.http://www.sciencedirect.com/science/article/pii/S097286001500033XArc-colouringς-kernelPanchromatic numberPanchromatic digraph |
| spellingShingle | Hortensia Galeana-Sánchez Micael Toledo New classes of panchromatic digraphs AKCE International Journal of Graphs and Combinatorics Arc-colouring ς-kernel Panchromatic number Panchromatic digraph |
| title | New classes of panchromatic digraphs |
| title_full | New classes of panchromatic digraphs |
| title_fullStr | New classes of panchromatic digraphs |
| title_full_unstemmed | New classes of panchromatic digraphs |
| title_short | New classes of panchromatic digraphs |
| title_sort | new classes of panchromatic digraphs |
| topic | Arc-colouring ς-kernel Panchromatic number Panchromatic digraph |
| url | http://www.sciencedirect.com/science/article/pii/S097286001500033X |
| work_keys_str_mv | AT hortensiagaleanasanchez newclassesofpanchromaticdigraphs AT micaeltoledo newclassesofpanchromaticdigraphs |