Determining the total colouring number is NP-hard
From MaRDI portal
Publication:909667
DOI10.1016/0012-365X(89)90187-8zbMath0695.05023MaRDI QIDQ909667
Publication date: 1989
Published in: Discrete Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items (64)
Colouring simplicial complexes via the Lechuga-Murillo's model ⋮ Total chromatic number of {square,unichord}-free graphs ⋮ On the total coloring of generalized Petersen graphs ⋮ Equitable total chromatic number of \(K_{r \times p}\) for \(p\) even ⋮ Even-power of cycles with many vertices are type 1 total colorable ⋮ On the equitable total chromatic number of cubic graphs ⋮ A note on the minimum total coloring of planar graphs ⋮ Total coloring of certain classes of product graphs ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ On total coloring of some classes of regular graphs ⋮ On total and edge coloring some Kneser graphs ⋮ A result on the total colouring of powers of cycles ⋮ Determining equitable total chromatic number for infinite classes of complete \(r\)-partite graphs ⋮ Edge-colouring and total-colouring chordless graphs ⋮ Equitable total coloring of complete $r$-partite $p$-balanced graphs ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Total coloring and total matching: polyhedra and facets ⋮ Total chromatic number of generalized Mycielski graphs ⋮ Total coloring of planar graphs without 6-cycles ⋮ Results about the total chromatic number and the conformability of some families of circulant graphs ⋮ Total coloring of planar graphs without some adjacent cycles ⋮ Weakening total coloring conjecture and Hadwiger's conjecture on total graphs ⋮ Total coloring of embedded graphs of maximum degree at least ten ⋮ Total colorings-a survey ⋮ Various matching keys for asymmetric topology encryption ⋮ On the conformability of regular line graphs ⋮ Minimum total coloring of planar graphs with maximum degree 8 ⋮ The total chromatic number of split-indifference graphs ⋮ Total coloring of rooted path graphs ⋮ Total chromatic number of unichord-free graphs ⋮ Enumerating the edge-colourings and total colourings of a regular graph ⋮ Unnamed Item ⋮ The hunting of a snark with total chromatic number 5 ⋮ Minimum total coloring of planar graph ⋮ COLORING ALGORITHMS ON SUBCUBIC GRAPHS ⋮ An Algorithmic Approach to Equitable Total Chromatic Number of Graphs ⋮ Total colorings of planar graphs without small cycles ⋮ 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 coloring of planar graphs without adjacent short cycles ⋮ A totally \((\Delta + 1)\)-colorable 1-planar graph with girth at least five ⋮ The total chromatic number of graphs having large maximum degree ⋮ Recent results on the total chromatic number ⋮ \([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 ⋮ List total colorings of series-parallel graphs ⋮ Edge and total coloring of interval graphs ⋮ Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds ⋮ Total and fractional total colourings of circulant graphs ⋮ Equitable total coloring of corona of cubic graphs ⋮ The total chromatic number of pseudo-Halin graphs with lower degree ⋮ Equitable total coloring of \(C_m\square C_n\) ⋮ Unnamed Item ⋮ Total colorings and list total colorings of planar graphs without intersecting 4-cycles ⋮ A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES ⋮ Compositions, decompositions, and conformability for total coloring on power of cycle graphs ⋮ Totally critical even order graphs ⋮ The total chromatic number of some bipartite graphs ⋮ Total colouring regular bipartite graphs is NP-hard ⋮ Total colorings of circulant graphs ⋮ Total coloring of quasi-line graphs and inflated graphs ⋮ Recent developments in total colouring
Cites Work
This page was built for publication: Determining the total colouring number is NP-hard
