Coloring the edges of a directed graph

DOI10.1007/S13226-014-0061-ZMaRDI QIDQ2353348zbMATH OpenOpenAlexFDO

Authors Sándor Szabó, Bogdán Zaválnij

Publication date 9 July 2015

Published in Indian Journal of Pure \& Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s13226-014-0061-z

zbMATH Keywords

cliquecoloring the edgescoloring the nodesdirected graphgraph coloringmaximum cliquemaximum tournamentNP-complete problemstournamenttransitive tournament

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

One of the interesting and important discrete mathematics problems is finding large cliques in graphs, which corresponds with finding subtournaments in digraphs. It is known that coloring the graph makes finding the large cliques much easier. The authors present colorings that facilitate the searching of subtournament in digraphs.

Recommendations

• Coloring the nodes of a directed graph
• Edge coloring of graphs, uses, limitation, complexity
• Vertex coloring edge-weighted digraphs
• The complexity of an exotic edge coloring of graphs
• A note on total colourings of digraphs

Cites work

• A fast algorithm for the maximum clique problem
• Algorithms for finding maximum transitive subtournaments
• An exact algorithm for the maximum clique problem
• An improved branch and bound algorithm for the maximum clique problem
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• scientific article; zbMATH DE number 3221981 (Why is no real title available?)
• scientific article; zbMATH DE number 3303831 (Why is no real title available?)
• scientific article; zbMATH DE number 2226810 (Why is no real title available?)
• On Sets of Consistent Arcs in a Tournament
• The Voting Problem

Cited in

(3)

• Coloring the nodes of a directed graph
• An Edge-Colored Version of Dirac's Theorem
• Algorithms for finding maximum transitive subtournaments

Describes a project that uses

Uses Software

• MaxCliqueDyn

This page was built for publication: Coloring the edges of a directed graph

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