BROWSE

Related Scientist

wiederrecht,sebastian's photo.

wiederrecht,sebastian
이산수학그룹
more info

ITEM VIEW & DOWNLOAD

Colouring non-even digraphs

Cited 0 time in webofscience Cited 0 time in scopus
186 Viewed 0 Downloaded
Title
Colouring non-even digraphs
Author(s)
Millani, Marcelo Garlet; Steiner, Raphael; Sebastian Wiederrecht
Publication Date
2022-10
Journal
Electronic Journal of Combinatorics, v.29, no.4
Publisher
Australian National University
Abstract
© The authors. Released under the CC BY-ND license (International 4.0).A colouring of a digraph as defined by Neumann-Lara in 1982 is a vertex-colouring such that no monochromatic directed cycles exist. The minimal number of colours required for such a colouring of a loopless digraph is defined to be its dichromatic number. This quantity has been widely studied in the last decades and can be considered as a natural directed analogue of the chromatic number of a graph. A digraph D is called even if for every 0-1-weighting of the edges it contains a directed cycle of even total weight. We show that every non-even digraph has dichromatic number at most 2 and an optimal colouring can be found in polynomial time. We strengthen a previously known NP-hardness result by showing that deciding whether a directed graph is 2-colourable remains NP-hard even if it contains a feedback vertex set of bounded size.
URI
https://pr.ibs.re.kr/handle/8788114/12696
DOI
10.37236/8800
ISSN
1077-8926
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse