Cover Image

A dichotomy theorem for $Γ$-switchable $H$-colouring on $m$-edge coloured graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Brewster, Richard, Kidner, Arnott, MacGillivray, Gary
Format:	Preprint
Published:	2023
Subjects:	Combinatorics Computational Complexity 05C15 05C60 68R10
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Colourings of $(m, n)$-coloured mixed graphs
by: MacGillivray, Gary, et al.
Published: (2020)

The complexity of frugal digraph homomorphisms
by: Bard, Stefan, et al.
Published: (2026)

Homomorphically Full Oriented Graphs
by: Bellitto, Thomas, et al.
Published: (2022)

The m-th Longest Runs of Multivariate Random Sequences
by: Kong, Yong
Published: (2024)

Hamiltonicity of Bell and Stirling Colour Graphs
by: Finbow, Stephen, et al.
Published: (2025)

Distributions of successions of arbitrary multisets
by: Kong, Yong
Published: (2024)

Reconstructing a graph from its Bell colouring graph
by: Hearn, Brian
Published: (2026)

Joint distribution of rises, falls, and number of runs in random sequences
by: Kong, Yong
Published: (2024)

Multiple consecutive runs of multi-state trials: distributions of $(k_1, k_2, \dots, k_\ell)$ patterns
by: Kong, Yong
Published: (2024)

Three-edge-coloring (Tait coloring) cubic graphs on the torus: A proof of Grünbaum's conjecture
by: Inoue, Yuta, et al.
Published: (2025)

Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color Theorem
by: Inoue, Yuta, et al.
Published: (2024)

Castling tree of tight Dyck nests with applications to odd and middle-levels graphs
by: Dejter, Italo J.
Published: (2023)

On complexity of substructure connectivity and restricted connectivity of graphs
by: Lü, Huazhong, et al.
Published: (2021)

Minimal obstructions to $C_5$-coloring in hereditary graph classes
by: Goedgebeur, Jan, et al.
Published: (2024)

An NP-hardness result for the colored constrained maximum 2-edge-colorable subgraph problem in bipartite graphs
by: Mkrtchyan, Vahan
Published: (2024)

Three results towards the approximation of special maximum matchings in graphs
by: Mkrtchyan, Vahan
Published: (2024)

Flip colouring of graphs II
by: Mifsud, Xandru
Published: (2024)

Circular-arc H-graphs: Ordering Characterizations and Forbidden Patterns
by: Paul, Indrajit, et al.
Published: (2025)

Symmetry classes of Hamiltonian cycles
by: Baligacs, Julia, et al.
Published: (2025)

Colouring random graphs: Tame colourings
by: Heckel, Annika, et al.
Published: (2023)

A note on interval colourings of graphs
by: Axenovich, Maria, et al.
Published: (2023)

Backbone coloring for graphs with degree 4
by: Michalik, Krzysztof, et al.
Published: (2024)

Simultaneous edge-colourings
by: Boyadzhiyska, Simona, et al.
Published: (2024)

On list extensions of the majority edge colourings
by: Pękała, Paweł, et al.
Published: (2025)

Limits of degeneracy for colouring graphs with forbidden minors
by: Norin, Sergey, et al.
Published: (2023)

A Linear Kernel for Independent Set Reconfiguration in Planar Graphs
by: Bousquet, Nicolas, et al.
Published: (2025)

On dispersability of some circulant graphs
by: Kainen, Paul C., et al.
Published: (2021)

Berge's conjecture for cubic graphs with small colouring defect
by: Karabáš, Ján, et al.
Published: (2022)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
by: Ahn, Jungho, et al.
Published: (2022)

Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
by: Furmańczyk, Hanna, et al.
Published: (2020)

Reconfiguration of Independent Transversals
by: Buys, Pjotr, et al.
Published: (2024)

The vertex Folkman number $F_v(3,3;5)$ equals~$8$
by: Niu, Tong
Published: (2026)

$2$-polarity and algorithmic aspects of polarity variants on cograph superclasses
by: Contreras-Mendoza, Fernando Esteban, et al.
Published: (2022)

Partitioning 2-edge-coloured bipartite graphs into monochromatic cycles
by: Benevides, Fabrício Siqueira, et al.
Published: (2024)

A note on graphs of $k$-colourings
by: Hogan, Emma, et al.
Published: (2024)

Counting subgraphs of coloring graphs using shadow graphs
by: MacLean, Simon
Published: (2025)

Reconstructing random pictures
by: Narayanan, Bhargav, et al.
Published: (2022)

Dirac's theorem and the switch geometry of perfect matchings
by: Kang, Ross J., et al.
Published: (2026)

Metric representations by minimal graphs
by: Franco-Sánchez, Víctor, et al.
Published: (2026)

Regular colouring defect of a cubic graph and the conjectures of Fan-Raspaud and Fulkerson
by: Karabáš, Ján, et al.
Published: (2023)