On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs
We prove that the game-perfect digraphs defined by Andres (2012) with regard to a digraph version of the maker-breaker graph colouring game introduced by Bodlaender (1991) always have a kernel. Furthermore, we introduce weakly game-perfect digraphs related to another digraph version of Bodlaender’s...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2020-01-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1016/j.akcej.2019.03.020 |
| _version_ | 1819060815116894208 |
|---|---|
| author | Stephan Dominique Andres |
| author_facet | Stephan Dominique Andres |
| author_sort | Stephan Dominique Andres |
| collection | DOAJ |
| description | We prove that the game-perfect digraphs defined by Andres (2012) with regard to a digraph version of the maker-breaker graph colouring game introduced by Bodlaender (1991) always have a kernel. Furthermore, we introduce weakly game-perfect digraphs related to another digraph version of Bodlaender’s graph colouring game, which was defined by Yang and Zhu (2010), and characterise the classes of weakly game-perfect digraphs by means of the classes of undirected game-perfect graphs. |
| first_indexed | 2024-12-21T14:32:59Z |
| format | Article |
| id | doaj.art-2771b8157ca2465e8670dfb83c45a0a9 |
| institution | Directory Open Access Journal |
| issn | 0972-8600 2543-3474 |
| language | English |
| last_indexed | 2024-12-21T14:32:59Z |
| publishDate | 2020-01-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-2771b8157ca2465e8670dfb83c45a0a92022-12-21T19:00:25ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002543-34742020-01-0117153954910.1016/j.akcej.2019.03.0201760670On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphsStephan Dominique Andres0Faculty of Mathematics and Computer Science, Fern Universität in Hagen, IZ, Universitätsstr. 1We prove that the game-perfect digraphs defined by Andres (2012) with regard to a digraph version of the maker-breaker graph colouring game introduced by Bodlaender (1991) always have a kernel. Furthermore, we introduce weakly game-perfect digraphs related to another digraph version of Bodlaender’s graph colouring game, which was defined by Yang and Zhu (2010), and characterise the classes of weakly game-perfect digraphs by means of the classes of undirected game-perfect graphs.http://dx.doi.org/10.1016/j.akcej.2019.03.020game-perfect digraphgame-perfect graphgame chromatic numberkernelperfect digraph |
| spellingShingle | Stephan Dominique Andres On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs AKCE International Journal of Graphs and Combinatorics game-perfect digraph game-perfect graph game chromatic number kernel perfect digraph |
| title | On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs |
| title_full | On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs |
| title_fullStr | On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs |
| title_full_unstemmed | On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs |
| title_short | On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs |
| title_sort | on kernels in strongly game perfect digraphs and a characterisation of weakly game perfect digraphs |
| topic | game-perfect digraph game-perfect graph game chromatic number kernel perfect digraph |
| url | http://dx.doi.org/10.1016/j.akcej.2019.03.020 |
| work_keys_str_mv | AT stephandominiqueandres onkernelsinstronglygameperfectdigraphsandacharacterisationofweaklygameperfectdigraphs |