BROWSE

Related Scientist

wiederrecht,sebastian's photo.

wiederrecht,sebastian
이산수학그룹
more info

ITEM VIEW & DOWNLOAD

Colouring non-even digraphs

DC Field Value Language
dc.contributor.authorMillani, Marcelo Garlet-
dc.contributor.authorSteiner, Raphael-
dc.contributor.authorSebastian Wiederrecht-
dc.date.accessioned2023-01-26T02:42:50Z-
dc.date.available2023-01-26T02:42:50Z-
dc.date.created2022-10-29-
dc.date.issued2022-10-
dc.identifier.issn1077-8926-
dc.identifier.urihttps://pr.ibs.re.kr/handle/8788114/12696-
dc.description.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.-
dc.language영어-
dc.publisherAustralian National University-
dc.titleColouring non-even digraphs-
dc.typeArticle-
dc.type.rimsART-
dc.identifier.wosid000870990400001-
dc.identifier.scopusid2-s2.0-85139247928-
dc.identifier.rimsid79027-
dc.contributor.affiliatedAuthorSebastian Wiederrecht-
dc.identifier.doi10.37236/8800-
dc.identifier.bibliographicCitationElectronic Journal of Combinatorics, v.29, no.4-
dc.relation.isPartOfElectronic Journal of Combinatorics-
dc.citation.titleElectronic Journal of Combinatorics-
dc.citation.volume29-
dc.citation.number4-
dc.type.docTypeArticle-
dc.description.journalClass1-
dc.description.journalClass1-
dc.description.isOpenAccessN-
dc.description.journalRegisteredClassscie-
dc.description.journalRegisteredClassscopus-
dc.relation.journalResearchAreaMathematics-
dc.relation.journalWebOfScienceCategoryMathematics, Applied-
dc.relation.journalWebOfScienceCategoryMathematics-
dc.subject.keywordPlusPFAFFIAN ORIENTATIONS-
dc.subject.keywordPlusPERMANENTS-
dc.subject.keywordPlusNUMBER-
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