Determining the total colouring number is NP-hard

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Recommendations

Total colouring regular bipartite graphs is NP-hard
NP-completeness of edge-colouring some restricted graphs
scientific article; zbMATH DE number 165470
The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3
Approximation of 3-Edge-Coloring of Cubic Graphs

Cites work

scientific article; zbMATH DE number 3639144 (Why is no real title available?)
NP completeness of finding the chromatic index of regular graphs
The NP-Completeness of Edge-Coloring

Cited in

(78)

Total coloring of planar graphs without adjacent short cycles
A polynomial-time algorithm for finding total colorings of partial $k$-trees
Total chromatic number of generalized Mycielski graphs
Recent results on the total chromatic number
Graceful colorings of graphs with maximum degree three
Minimum total coloring of planar graph
On the total coloring of generalized Petersen graphs
Total colorings of planar graphs without small cycles
COLORING ALGORITHMS ON SUBCUBIC GRAPHS
On total chromatic number of direct product graphs
Total chromatic number for certain classes of product graphs
Total colorings-a survey
The total-chromatic number of some families of snarks
Total coloring of planar graphs without 6-cycles
Total chromatic number of unichord-free graphs
On total and edge coloring some Kneser graphs
Colorings with few colors: counting, enumeration and combinatorial bounds
Total colorings and list total colorings of planar graphs without intersecting 4-cycles
Colouring simplicial complexes via the Lechuga-Murillo's model
Equitable total coloring of Fibonacci graphs
Equitable total chromatic number of $K_{r \times p}$ for $p$ even
On the equitable total chromatic number of cubic graphs
Total colorings of circulant graphs
Equitable total coloring of complete $r$-partite $p$-balanced graphs
An algorithmic approach to equitable total chromatic number of graphs
Total chromatic number for certain classes of lexicographic product graphs
Equitable total coloring of corona of cubic graphs
Enumerating the edge-colourings and total colourings of a regular graph
Determining equitable total chromatic number for infinite classes of complete $r$-partite graphs
Totally critical even order graphs
Total chromatic number of \{square,unichord\}-free graphs
Various matching keys for asymmetric topology encryption
On the conformability of regular line graphs
A note on the minimum total coloring of planar graphs
Total coloring of certain classes of product graphs
Minimum total coloring of planar graphs with maximum degree 8
Total coloring of quasi-line graphs and inflated graphs
Filling some gaps on the edge coloring problem of split graphs
Recent developments in total colouring
The total chromatic number of graphs having large maximum degree
Total coloring of embedded graphs of maximum degree at least ten
On total coloring of some classes of regular graphs
Total coloring of circulant graphs C_n(1,4)
Total coloring and total matching: polyhedra and facets
The hunting of a snark with total chromatic number 5
Edge and total coloring of interval graphs
Complexity of (p,1)-total labelling
Equitable total coloring of C_m C_n
Total and fractional total colourings of circulant graphs
A sufficient condition for complete multipartite graphs to be of type 1
The total chromatic number of some bipartite graphs
Results about the total chromatic number and the conformability of some families of circulant graphs
New results on edge-coloring and total-coloring of split graphs
Total colorings of some classes of four regular circulant graphs
Total colouring regular bipartite graphs is NP-hard
Complexity-separating graph classes for vertex, edge and total colouring
On efficient total colorings of regular graphs
A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs
A result on the total colouring of powers of cycles
$[r,s,t]$-coloring of trees and bipartite graphs
scientific article; zbMATH DE number 3906534 (Why is no real title available?)
Approximation of 3-Edge-Coloring of Cubic Graphs
The total chromatic number of pseudo-Halin graphs with lower degree
Total colorings of k-regular graphs of girths 2k and k
Complexity of approximation of 3-edge-coloring of graphs
Weakening total coloring conjecture and Hadwiger's conjecture on total graphs
Colorings with few colors: counting, enumeration and combinatorial bounds
A totally $(\Delta + 1)$-colorable 1-planar graph with girth at least five
Total coloring of planar graphs without some adjacent cycles
Total coloring of rooted path graphs
Edge-colouring and total-colouring chordless graphs
List total colorings of series-parallel graphs
The total chromatic number of split-indifference graphs
scientific article; zbMATH DE number 2230202 (Why is no real title available?)
Compositions, decompositions, and conformability for total coloring on power of cycle graphs
Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs
Total coloring of some graph operations
Even-power of cycles with many vertices are type 1 total colorable

This page was built for publication: Determining the total colouring number is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q909667)