Edge-colouring and total-colouring chordless graphs
From MaRDI portal
Publication:389214
DOI10.1016/j.disc.2013.03.020zbMath1408.05063arXiv1309.1842OpenAlexW1965850005MaRDI QIDQ389214
Nicolas Trotignon, Celina M. Herrera de Figueiredo, Raphael C. S. Machado
Publication date: 20 January 2014
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1309.1842
Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (15)
Complexity separating classes for edge-colouring and total-colouring ⋮ The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs ⋮ The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring ⋮ Characterizing k-chordal unichord-free graphs ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Acyclic chromatic index of chordless graphs ⋮ Total colorings-a survey ⋮ Strongly unichord-free graphs ⋮ Graph edge coloring: a survey ⋮ Classifying \(k\)-edge colouring for \(H\)-free graphs ⋮ Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs ⋮ Two complexity results for the vertex coloring problem ⋮ Using SPQR-trees to speed up recognition algorithms based on 2-cutsets ⋮ Wheel-free planar graphs ⋮ Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs
Uses Software
Cites Work
- Total-chromatic number and chromatic index of dually chordal graphs
- The total chromatic number of split-indifference graphs
- On graphs with no induced subdivision of \(K_4\)
- Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs
- Total chromatic number of unichord-free graphs
- Total 4-choosability of series-parallel graphs
- Edge and total choosability of near-outerplanar graphs
- Determining the total colouring number is NP-hard
- Decompositions for edge-coloring join graphs and cobipartite graphs
- NP-completeness of edge-colouring some restricted graphs
- Total colouring regular bipartite graphs is NP-hard
- List edge and list total colourings of multigraphs
- Characterizing and edge-colouring split-indifference graphs
- Decompositions for the edge colouring of reduced indifference graphs.
- Planar graphs of maximum degree seven are Class I
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Total colourings of graphs
- Chromatic index of graphs with no cycle with a unique chord
- Edge-colouring of join graphs
- The determination of the total chromatic number of series-parallel graphs with \((G) \geq 4\)
- Total chromatic number of one kind of join graphs
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Total chromatic number of planar graphs with maximum degree ten
- The NP-completeness column: an ongoing guide
- The NP-Completeness of Edge-Coloring
- NP completeness of finding the chromatic index of regular graphs
- Graphs That Do Not Contain a Cycle with a Node That Has at Least Two Neighbors on It
- A structure theorem for graphs with no cycle with a unique chord and its consequences
- Minimally 2-connected graphs.
- On Minimal Blocks
- Edge and total coloring of interval graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Edge-colouring and total-colouring chordless graphs
