Total chromatic number of unichord-free graphs

DOI10.1016/j.dam.2011.03.024zbMath1228.05157OpenAlexW2081938755MaRDI QIDQ643026

Celina M. Herrera de Figueiredo, Raphael C. S. Machado

Publication date: 27 October 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.03.024

zbMATH Keywords

decompositionedge-colouringrecognitiontotal-colouringcycle with a unique chordheawood graphpetersen graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15)

Related Items (17)

Total-colorings of complete multipartite graphs using amalgamations ⋮ The homogeneous set sandwich problem ⋮ Complexity separating classes for edge-colouring and total-colouring ⋮ Characterizing k-chordal unichord-free graphs ⋮ New graph classes characterized by weak vertex separators and two-pairs ⋮ Edge-colouring and total-colouring chordless graphs ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ A new characterization of unichord-free graphs ⋮ Unnamed Item ⋮ Total colorings-a survey ⋮ Total coloring of rooted path graphs ⋮ Strongly unichord-free graphs ⋮ Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs ⋮ Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs ⋮ On the total and AVD-total coloring of graphs ⋮ Unique chords of unique cycles in 3-connected planar graphs ⋮ WHEN ALL MINIMAL VERTEX SEPARATORS INDUCE COMPLETE OR EDGELESS SUBGRAPHS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Total-chromatic number and chromatic index of dually chordal graphs
• The strong perfect graph theorem
• Total 4-choosability of series-parallel graphs
• Edge and total choosability of near-outerplanar graphs
• A result on the total colouring of powers of cycles
• Determining the total colouring number is NP-hard
• NP-completeness of edge-colouring some restricted graphs
• The total coloring of a multigraph with maximal degree 4
• Total colouring regular bipartite graphs is NP-hard
• The total chromatic number of any multigraph with maximum degree five is at most seven
• List edge and list total colourings of multigraphs
• Vertex colouring and forbidden subgraphs -- a survey
• Total colourings of graphs
• Chromatic index of graphs with no cycle with a unique chord
• The determination of the total chromatic number of series-parallel graphs with \((G) \geq 4\)
• Total chromatic number of one kind of join graphs
• On the total coloring of certain graphs
• Total chromatic number of {square,unichord}-free graphs
• Total chromatic number of planar graphs with maximum degree ten
• The NP-Completeness of Edge-Coloring
• NP completeness of finding the chromatic index of regular graphs
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• On Total Chromatic Number of a Graph
• Edge and total coloring of interval graphs

This page was built for publication: Total chromatic number of unichord-free graphs