Characterizing and edge-colouring split-indifference graphs

DOI10.1016/S0166-218X(97)00128-5zbMath0901.05043OpenAlexW1993232133MaRDI QIDQ1383379

Carmen Z. Ortiz, Jayme Luiz Szwarcfiter, Nelson F. Maculan

Publication date: 2 June 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

algorithmscharacterizationsplit graphschromatic indexperfect matchingedge colouringindifference graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)

Related Items (13)

Edge-colouring and total-colouring chordless graphs ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ On edge-colouring indifference graphs ⋮ The overfull conjecture on split-comparability and split-interval graphs ⋮ Edge Coloring of Split Graphs ⋮ Counting and enumerating unlabeled split–indifference graphs ⋮ The total chromatic number of split-indifference graphs ⋮ Classifying \(k\)-edge colouring for \(H\)-free graphs ⋮ Edge clique partition in \((k,\ell)\)-graphs ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ Partitioning a graph into complementary subgraphs ⋮ Chromatic index of graphs with no cycle with a unique chord ⋮ Vector domination in split-indifference graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP-completeness of edge-colouring some restricted graphs
• On the compatibility between a graph and a simple order
• On the edge-chromatic number of a graph
• Graphs which are vertex-critical with respect to the edge-chromatic number
• The NP-Completeness of Edge-Coloring
• On edge-colouring indifference graphs
• Multicoloring the incidentors of a weighted directed multigraph
• The Colour Numbers of Complete Graphs

This page was built for publication: Characterizing and edge-colouring split-indifference graphs