Coloring the edges of a directed graph

Sándor Szabó () and Bogdán Zavalnij ()
Additional contact information
Sándor Szabó: University of Pécs
Bogdán Zavalnij: University of Pécs

Indian Journal of Pure and Applied Mathematics, 2014, vol. 45, issue 2, 239-260

Abstract: Abstract Finding large cliques in a graph is an important problem in applied discrete mathematics. In directed graph a possible corresponding problem is finding large transitive subtournaments. It is well-known that coloring the graph speeds up the clique search in the undirected case. In this paper we propose coloring schemes to speed up the tournament search in the directed case. We prove two complexity results about the proposed colorings. A consequence of these results is that in practical computations we have to be content with approximate greedy coloring algorithms.

Keywords: Clique; maximum clique; graph coloring; coloring the nodes; coloring the edges; NP-complete problems; directed graph; tournament; transitive tournament; maximum tournament (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13226-014-0061-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:indpam:v:45:y:2014:i:2:d:10.1007_s13226-014-0061-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/13226

DOI: 10.1007/s13226-014-0061-z

Access Statistics for this article

Indian Journal of Pure and Applied Mathematics is currently edited by Nidhi Chandhoke

More articles in Indian Journal of Pure and Applied Mathematics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().