Decompositions for the edge colouring of reduced indifference graphs.

DOI10.1016/S0304-3975(02)00636-9MaRDI QIDQ1401296zbMATH OpenOpenAlexFDO

Authors João Meidanis, Célia P. de Mello, Carmen Z. Ortiz, Celina M. H. de Figueiredo

Publication date 17 August 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(02)00636-9

zbMATH Keywords

AlgorithmsGraph algorithmsIndifference graphsEdge colouring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Publication:4508371
• On edge-colouring indifference graphs
• On edge-colouring indifference graphs
• Characterizing and edge-colouring split-indifference graphs
• Recent progress on edge-colouring graphs

Cites work

• scientific article; zbMATH DE number 1463393 (Why is no real title available?)
• A constructive proof of Vizing's theorem
• A linear-time algorithm for proper interval graph recognition
• Clique graphs of time graphs
• Difference graphs
• Minimum proper interval graphs
• NP-completeness of edge-colouring some restricted graphs
• On edge-colouring indifference graphs
• On the compatibility between a graph and a simple order
• The NP-Completeness of Edge-Coloring
• Total-chromatic number and chromatic index of dually chordal graphs
• Two conjectures on edge-colouring

Cited in

(7)

• scientific article; zbMATH DE number 1512684 (Why is no real title available?)
• A connectivity-based decomposition for graph edge-colouring
• Decompositions to degree-constrained subgraphs are simply reducible to edge-colorings
• Edge-colouring and total-colouring chordless graphs
• Chromatic index of graphs with no cycle with a unique chord
• Minimal classes of graphs of unbounded clique-width
• Canonical antichains of unit interval and bipartite permutation graphs

This page was built for publication: Decompositions for the edge colouring of reduced indifference graphs.

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