Decomposing edge-coloured graphs under colour degree constraints

Shinya Fujita, Ruonan Li, Guanghui Wang*

*Corresponding author for this work

    Research output: Contribution to journalArticleAcademicpeer-review

    3 Citations (Scopus)

    Abstract

    For an edge-coloured graph G, the minimum colour degree of G means the minimum number of colours on edges which are incident to each vertex of G. We prove that if G is an edge-coloured graph with minimum colour degree at least 5, then V(G) can be partitioned into two parts such that each part induces a subgraph with minimum colour degree at least 2. We show this theorem by proving amuch stronger form. Moreover, we point out an important relationship between our theorem and Bermond and Thomassen's conjecture in digraphs.

    Original languageEnglish
    Pages (from-to)755-767
    Number of pages13
    JournalCombinatorics Probability and Computing
    Volume28
    Issue number5
    DOIs
    Publication statusPublished - 1 Sep 2019

    Fingerprint

    Dive into the research topics of 'Decomposing edge-coloured graphs under colour degree constraints'. Together they form a unique fingerprint.

    Cite this