Total colouring regular bipartite graphs is NP-hard
From MaRDI portal
Publication:1313834
DOI10.1016/0012-365X(92)00058-YzbMath0791.05042OpenAlexW1963612445MaRDI QIDQ1313834
Abdón Sánchez-Arroyo, Colin J. H. McDiarmid
Publication date: 28 June 1994
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(92)00058-y
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items (44)
Total chromatic number of {square,unichord}-free graphs ⋮ A note on the minimum total coloring of planar graphs ⋮ Total coloring of certain classes of product graphs ⋮ On the neighbour-distinguishing index of a graph ⋮ Complexity separating classes for edge-colouring and total-colouring ⋮ The parameterised complexity of list problems on graphs of bounded treewidth ⋮ A result on the total colouring of powers of cycles ⋮ Edge-colouring and total-colouring chordless graphs ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Total chromatic number of generalized Mycielski graphs ⋮ Total coloring of planar graphs without some adjacent cycles ⋮ Total coloring conjecture on certain classes of product graphs ⋮ The total chromatic number of split-indifference graphs ⋮ Total coloring of rooted path graphs ⋮ On total coloring the direct product of cycles and bipartite direct product of graphs ⋮ On defected colourings of graphs ⋮ Total chromatic number of unichord-free graphs ⋮ Unnamed Item ⋮ The hunting of a snark with total chromatic number 5 ⋮ Minimum total coloring of planar graph ⋮ COLORING ALGORITHMS ON SUBCUBIC GRAPHS ⋮ Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs ⋮ A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs ⋮ Total colorings of product graphs ⋮ Total coloring of planar graphs without adjacent short cycles ⋮ Recent results on the total chromatic number ⋮ Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs ⋮ \([r,s,t\)-coloring of trees and bipartite graphs] ⋮ The total-chromatic number of some families of snarks ⋮ Complexity of (p,1)-total labelling ⋮ On total chromatic number of direct product graphs ⋮ Total coloring conjecture for certain classes of graphs ⋮ Total and fractional total colourings of circulant graphs ⋮ On the total and AVD-total coloring of graphs ⋮ Equitable total coloring of \(C_m\square C_n\) ⋮ Unnamed Item ⋮ Graph coloring with cardinality constraints on the neighborhoods ⋮ Graph coloring: a novel heuristic based on trailing path-properties, perspective and applications in structured networks ⋮ Total tessellation cover: bounds, hardness, and applications ⋮ Compositions, decompositions, and conformability for total coloring on power of cycle graphs ⋮ The total chromatic number of some bipartite graphs ⋮ Total colorings of certain classes of lexicographic product graphs ⋮ Total colorings of circulant graphs ⋮ Total coloring of quasi-line graphs and inflated graphs
Cites Work
This page was built for publication: Total colouring regular bipartite graphs is NP-hard
