The NP-Completeness of Edge-Coloring

Previous article Next article The NP-Completeness of Edge-ColoringIan HolyerIan Holyerhttps: //doi. org/10. 1137/0210055PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstractWe show that it is NP-complete to determine the chromatic index of an arbitrary graph. The problem remains NP-complete even for cubic graphs. 1 S. Fiorini and, Robin James Wilson, Edge-colourings of graphs, Pitman, London, 1977iii+154 58: 27599 0421. 05023 Google Scholar2 Michael R. Garey and, David S. Johnson, Computers and intractability, W. H. Freeman and Co. , San Francisco, Calif. , 1979x+338 80g: 68056 0411. 68039 Google Scholar3 Rufus Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly, 82 (1975), 221–239 52: 2940 0311. 05109 CrossrefISIGoogle Scholar4 R. Isaacs, Loupekine's snarks: A bifamily of non-Tait-colorable graphs, unpublished Google ScholarKeywordscomputational complexityNP-complete problemschromatic indexedge-coloring Previous article Next article FiguresRelatedReferencesCited ByDetails Regular pattern-free coloringDiscrete Applied Mathematics, Vol. 321 | 1 Nov 2022 Cross Ref Chromatic index of dense quasirandom graphsJournal of Combinatorial Theory, Series B, Vol. 157 | 1 Nov 2022 Cross Ref Subcubic planar graphs of girth 7 are class IDiscrete Mathematics, Vol. 345, No. 10 | 1 Oct 2022 Cross Ref Independence number of edge‐chromatic critical graphsJournal of Graph Theory, Vol. 101, No. 2 | 20 March 2022 Cross Ref Complexity Dichotomy for List-5-Coloring with a Forbidden Induced SubgraphSepehr Hajebi, Yanjia Li, and Sophie SpirklSIAM Journal on Discrete Mathematics, Vol. 36, No. 3 | 30 August 2022AbstractPDF (592 KB) The Overfullness of Graphs with Small Minimum Degree and Large Maximum DegreeYan Cao, Guantao Chen, Guangming Jing, and Songling ShanSIAM Journal on Discrete Mathematics, Vol. 36, No. 3 | 13 September 2022AbstractPDF (395 KB) Vertex-Distinguishing Edge Colorings Of Some Complete Multipartite Graphs“Katchar” Collection of Scientific Articles International Scientific-Educational Center NAS RA | 22 September 2022 Cross Ref Orientation‐based edge‐colorings and linear arboricity of multigraphsJournal of Graph Theory, Vol. 11 | 20 September 2022 Cross Ref Edge coloring graphs with large minimum degreeJournal of Graph Theory, Vol. 244 | 18 September 2022 Cross Ref Switching 3-edge-colorings of cubic graphsDiscrete Mathematics, Vol. 345, No. 9 | 1 Sep 2022 Cross Ref Overfullness of critical class 2 graphs with a small core degreeJournal of Combinatorial Theory, Series B, Vol. 156 | 1 Sep 2022 Cross Ref Using the minimum maximum flow degree to approximate the flow coloring problemAnnals of Operations Research, Vol. 316, No. 2 | 30 June 2021 Cross Ref Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameterTheoretical Computer Science, Vol. 931 | 1 Sep 2022 Cross Ref An improvement to the Hilton-Zhao vertex-splitting conjectureDiscrete Mathematics, Vol. 345, No. 8 | 1 Aug 2022 Cross Ref Parameterized Complexity of Maximum Edge Colorable SubgraphAlgorithmica, Vol. 35 | 14 July 2022 Cross Ref On 3-Coloring of (2P₄, C₅) -Free GraphsAlgorithmica, Vol. 84, No. 6 | 15 February 2022 Cross Ref On the Nash number and the diminishing Grundy number of a graphDiscrete Applied Mathematics, Vol. 314 | 1 Jun 2022 Cross Ref Colouring graphs of bounded diameter in the absence of small cyclesDiscrete Applied Mathematics, Vol. 314 | 1 Jun 2022 Cross Ref How many matchings cover the nodes of a graph? Mathematical Programming, Vol. 81 | 31 May 2022 Cross Ref Kempe Equivalence Classes of Cubic Graphs Embedded on the Projective PlaneCombinatorica, Vol. 12 | 19 May 2022 Cross Ref Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter TopologiesIEEE INFOCOM 2022 - IEEE Conference on Computer Communications | 2 May 2022 Cross Ref Dichotomizing k -vertex-critical H -free graphs for H of order fourDiscrete Applied Mathematics, Vol. 312 | 1 May 2022 Cross Ref Approximate separable multichoice optimization over monotone systemsDiscrete Optimization, Vol. 44 | 1 May 2022 Cross Ref Weighted 2-sections and hypergraph reconstructionTheoretical Computer Science, Vol. 915 | 1 May 2022 Cross Ref Rolling weight-matching methods for the inter-satellite link assignment in global navigation satellite systemsGPS Solutions, Vol. 26, No. 2 | 19 January 2022 Cross Ref Characterization of saturated graphs related to pairs of disjoint matchingsIllinois Journal of Mathematics, Vol. 66, No. 1 | 1 Apr 2022 Cross Ref On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching NumberAlgorithmica, Vol. 309 | 22 March 2022 Cross Ref Colouring simplicial complexes via the Lechuga–Murillo’s modelApplicable Algebra in Engineering, Communication and Computing, Vol. 33, No. 2 | 12 June 2020 Cross Ref The smallest pair of cospectral cubic graphs with different chromatic indexesDiscrete Applied Mathematics, Vol. 309 | 1 Mar 2022 Cross Ref GAN-Based Pareto Optimization for Self-Healing of Radio Access Network SlicesIEEE Transactions on Network and Service Management, Vol. 19, No. 1 | 1 Mar 2022 Cross Ref Bounds for the Rainbow Disconnection Numbers of GraphsActa Mathematica Sinica, English Series, Vol. 38, No. 2 | 15 February 2022 Cross Ref Coloring temporal graphsJournal of Computer and System Sciences, Vol. 123 | 1 Feb 2022 Cross Ref A proof of the Erdös-Faber-Lovász conjecture: Algorithmic aspects2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) | 1 Feb 2022 Cross Ref Multi-Sender Index Coding Over Linear NetworksIEEE Communications Letters, Vol. 26, No. 2 | 1 Feb 2022 Cross Ref Open Shop Scheduling with Simultaneity ConstraintsA Book of Open Shop Scheduling | 31 October 2021 Cross Ref The Complexity of L (p, q) -Edge-LabellingWALCOM: Algorithms and Computation | 16 March 2022 Cross Ref Optimization of the Functional Decomposition of Parallel and Distributed Computations in Graph Coloring With the Use of High-Performance ComputingIEEE Access, Vol. 10 | 1 Jan 2022 Cross Ref On coloring a class of claw-free and hole-twin-free graphsDiscrete Applied Mathematics, Vol. 9 | 1 Nov 2021 Cross Ref The complexity of counting edge colorings for simple graphsTheoretical Computer Science, Vol. 889 | 1 Oct 2021 Cross Ref Complexity and algorithms for injective edge-coloring in graphsInformation Processing Letters, Vol. 170 | 1 Sep 2021 Cross Ref Your rugby mates don't need to know your colleagues: Triadic closure with edge colorsJournal of Computer and System Sciences, Vol. 120 | 1 Sep 2021 Cross Ref Decomposition of university course timetablingAnnals of Operations Research, Vol. 302, No. 2 | 25 October 2019 Cross Ref Disjointness graphs of segments in the spaceCombinatorics, Probability and Computing, Vol. 30, No. 4 | 4 November 2020 Cross Ref On Graph Coloring Analysis Through Visualization2021 International Conference on Information and Digital Technologies (IDT) | 22 Jun 2021 Cross Ref Revising Johnson’s table for the 21st centuryDiscrete Applied Mathematics, Vol. 3 | 1 Jun 2021 Cross Ref On Generalisations of the AVD Conjecture to DigraphsGraphs and Combinatorics, Vol. 37, No. 2 | 20 January 2021 Cross Ref Fly-path: Traffic-based multi-hop routing approach for hybrid wireless data centersComputer Communications, Vol. 170 | 1 Mar 2021 Cross Ref On the average degree of edge chromatic critical graphsJournal of Combinatorial Theory, Series B, Vol. 147 | 1 Mar 2021 Cross Ref Algorithmic Aspects of the Maximum 2-edge-colorable Subgraph ProblemAdvanced Information Networking and Applications | 1 May 2021 Cross Ref Colouring Graphs of Bounded Diameter in the Absence of Small CyclesAlgorithms and Complexity | 4 May 2021 Cross Ref Applications and ExtensionsGuide to Graph Colouring | 8 October 2021 Cross Ref Colorability in Line GraphsLine Graphs and Line Digraphs | 23 July 2021 Cross Ref Bears with Hats and Independence PolynomialsGraph-Theoretic Concepts in Computer Science | 20 September 2021 Cross Ref On 3-Coloring of (2P₄, C₅) -Free GraphsGraph-Theoretic Concepts in Computer Science | 20 September 2021 Cross Ref Disjoint Stable Matchings in Linear TimeGraph-Theoretic Concepts in Computer Science | 20 September 2021 Cross Ref Allocating Indivisible Items with Minimum Dissatisfaction on Preference GraphsAlgorithmic Decision Theory | 27 October 2021 Cross Ref New Steiner 2-designs from old ones by paramodificationsDiscrete Applied Mathematics, Vol. 288 | 1 Jan 2021 Cross Ref Superposition of snarks revisitedEuropean Journal of Combinatorics, Vol. 91 | 1 Jan 2021 Cross Ref The chromatic index of split-interval graphsProcedia Computer Science, Vol. 195 | 1 Jan 2021 Cross Ref Coverability of Graphs by Parity Regular SubgraphsMathematics, Vol. 9, No. 2 | 18 January 2021 Cross Ref Better 3-coloring algorithms: Excluding a triangle and a seven vertex pathTheoretical Computer Science, Vol. 850 | 1 Jan 2021 Cross Ref Evolution through segmental duplications and losses: a Super-Reconciliation approachAlgorithms for Molecular Biology, Vol. 15, No. 1 | 26 May 2020 Cross Ref Restricted extension of sparse partial edge colorings of hypercubesDiscrete Mathematics, Vol. 343, No. 11 | 1 Nov 2020 Cross Ref Grundy coloring in some subclasses of bipartite graphs and their complementsInformation Processing Letters, Vol. 163 | 1 Nov 2020 Cross Ref High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and QualitySC20: International Conference for High Performance Computing, Networking, Storage and Analysis | 1 Nov 2020 Cross Ref Complete Complexity Dichotomy for 7 -Edge Forbidden Subgraphs in the Edge Coloring ProblemJournal of Applied and Industrial Mathematics, Vol. 14, No. 4 | 29 January 2021 Cross Ref Graph fractal dimension and the structure of fractal networksJournal of Complex Networks, Vol. 8, No. 4 | 18 November 2020 Cross Ref 1‐Factorizations of pseudorandom graphsRandom Structures & Algorithms, Vol. 57, No. 2 | 21 May 2020 Cross Ref Connected greedy coloring of H -free graphsDiscrete Applied Mathematics, Vol. 284 | 1 Sep 2020 Cross Ref On determining when small embeddings of partial Steiner triple systems existJournal of Combinatorial Designs, Vol. 28, No. 8 | 17 March 2020 Cross Ref b-continuity and partial Grundy coloring of graphs with large girthDiscrete Mathematics, Vol. 343, No. 8 | 1 Aug 2020 Cross Ref Colouring (Pr + Ps) -Free GraphsAlgorithmica, Vol. 82, No. 7 | 25 January 2020 Cross Ref A 52-approximation algorithm for coloring rooted subtrees of a degree 3 treeJournal of Combinatorial Optimization, Vol. 40, No. 1 | 9 April 2020 Cross Ref Complexity-separating graph classes for vertex, edge and total colouringDiscrete Applied Mathematics, Vol. 281 | 1 Jul 2020 Cross Ref Edge-colouring graphs with bounded local degree sumsDiscrete Applied Mathematics, Vol. 281 | 1 Jul 2020 Cross Ref On the complexity of cd-coloring of graphsDiscrete Applied Mathematics, Vol. 280 | 1 Jun 2020 Cross Ref Co-density and fractional edge cover packingJournal of Combinatorial Optimization, Vol. 39, No. 4 | 4 February 2020 Cross Ref On the Relation of Strong Triadic Closure and Cluster DeletionAlgorithmica, Vol. 82, No. 4 | 16 August 2019 Cross Ref Group connectivity: Z4 vs Z22Journal of Graph Theory, Vol. 93, No. 3 | 28 August 2019 Cross Ref The multi-league sports scheduling problem, or how to schedule thousands of matchesOperations Research Letters, Vol. 48, No. 2 | 1 Mar 2020 Cross Ref Mixed Graph Colorings: A Historical ReviewMathematics, Vol. 8, No. 3 | 9 March 2020 Cross Ref A QoS‐aware energy‐efficient memetic flower pollination routing protocol for underwater acoustic sensor networkConcurrency and Computation: Practice and Experience, Vol. 32, No. 4 | 13 February 2019 Cross Ref Distributed Edge Coloring and a Special Case of the Constructive Lovász Local LemmaACM Transactions on Algorithms, Vol. 16, No. 1 | 11 Jan 2020 Cross Ref Obstructions for Three-Coloring and List Three-Coloring H-Free GraphsMaria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, and Mingxian ZhongSIAM Journal on Discrete Mathematics, Vol. 34, No. 1 | 19 February 2020AbstractPDF (669 KB) Hardness and Ease of Curing the Sign Problem for Two-Local Qubit HamiltoniansJoel Klassen, Milad Marvian, Stephen Piddock, Marios Ioannou, Itay Hen, and Barbara M. TerhalSIAM Journal on Computing, Vol. 49, No. 6 | 17 December 2020AbstractPDF (701 KB) Parameterized Complexity of Maximum Edge Colorable SubgraphComputing and Combinatorics | 27 August 2020 Cross Ref The Complexity of the Partition Coloring ProblemTheory and Applications of Models of Computation | 9 October 2020 Cross Ref Fully Dynamic Graph Algorithms Inspired by Distributed ComputingACM Journal of Experimental Algorithmics, Vol. 24 | 17 Dec 2019 Cross Ref Colouring square-free graphs without long induced pathsJournal of Computer and System Sciences, Vol. 106 | 1 Dec 2019 Cross Ref Low-cost quantum circuits for classically intractable instances of the Hamiltonian dynamics simulation problemnpj Quantum Information, Vol. 5, No. 1 | 27 May 2019 Cross Ref Tight Bounds for Online Edge Coloring2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) | 1 Nov 2019 Cross Ref Optimization design for parallel coloring of a set of graphs in the High-Performance Computing2019 IEEE 15th International Scientific Conference on Informatics | 1 Nov 2019 Cross Ref Goldberg's conjecture is true for random multigraphsJournal of Combinatorial Theory, Series B, Vol. 138 | 1 Sep 2019 Cross Ref Puzzle—More Logic Puzzle Apps Solved by Mathematical ProgrammingINFORMS Transactions on Education, Vol. 20, No. 1 | 1 Sep 2019 Cross Ref Approximately Coloring Graphs Without Long Induced PathsAlgorithmica, Vol. 81, No. 8 | 26 April 2019 Cross Ref H -colouring Pt -free graphs in subexponential timeDiscrete Applied Mathematics, Vol. 267 | 1 Aug 2019 Cross Ref The Chromatic Index of Proper Circular-arc Graphs of Odd Maximum Degree which are ChordalElectronic Notes in Theoretical Computer Science, Vol. 346 | 1 Aug 2019 Cross Ref On Coloring a Class of Claw-free GraphsElectronic Notes in Theoretical Computer Science, Vol. 346 | 1 Aug 2019 Cross Ref Weighted and locally bounded list-colorings in split graphs, cographs, and partial k-treesTheoretical Computer Science, Vol. 782 | 1 Aug 2019 Cross Ref On strong proper connection number of cubic graphsDiscrete Applied Mathematics, Vol. 265 | 1 Jul 2019 Cross Ref Perfect 1-factorizationsMathematica Slovaca, Vol. 69, No. 3 | 21 May 2019 Cross Ref Classifying k-edge colouring for H-free graphsInformation Processing Letters, Vol. 146 | 1 Jun 2019 Cross Ref An upper bound for the choice number of star edge coloring of graphsApplied Mathematics and Computation, Vol. 348 | 1 May 2019 Cross Ref Certifying coloring algorithms for graphs without long induced pathsDiscrete Applied Mathematics, Vol. 261 | 1 May 2019 Cross Ref Independent Feedback Vertex Set for P₅ P 5 -Free GraphsAlgorithmica, Vol. 81, No. 4 | 26 June 2018 Cross Ref Detecting an induced subdivision of K4Journal of Graph Theory, Vol. 90, No. 2 | 25 June 2018 Cross Ref Graphs with small fall-spectrumDiscrete Applied Mathematics, Vol. 254 | 1 Feb 2019 Cross Ref Algorithmic problems in right-angled Artin groups: Complexity and applicationsJournal of Algebra, Vol. 519 | 1 Feb 2019 Cross Ref Densities, Matchings, and Fractional Edge-ColoringsXujin Chen, Wenan Zang, and Qiulan ZhaoSIAM Journal on Optimization, Vol. 29, No. 1 | 22 January 2019AbstractPDF (504 KB) The Hilton--Zhao Conjecture is True for Graphs with Maximum Degree 4Daniel W. Cranston and Landon RabernSIAM Journal on Discrete Mathematics, Vol. 33, No. 3 | 11 July 2019AbstractPDF (351 KB) Multi-channel Assignment and Link Scheduling for Prioritized Latency-Sensitive ApplicationsAlgorithms for Sensor Systems | 5 November 2019 Cross Ref Graph Edge Coloring: A SurveyGraphs and Combinatorics, Vol. 35, No. 1 | 4 January 2019 Cross Ref List-edge-colouring planar graphs with precoloured edgesEuropean Journal of Combinatorics, Vol. 75 | 1 Jan 2019 Cross Ref Space-efficient Euler partition and bipartite edge coloringTheoretical Computer Science, Vol. 754 | 1 Jan 2019 Cross Ref Complexity of edge coloring with minimum reload/changeover costsNetworks, Vol. 38 | 7 December 2018 Cross Ref Improved Process of Running Tasks in the High Performance Computing System2018 16th International Conference on Emerging eLearning Technologies and Applications (ICETA) | 1 Nov 2018 Cross Ref Minimum multiplicity edge coloring via orientationDiscrete Applied Mathematics, Vol. 247 | 1 Oct 2018 Cross Ref 1-Factorizations of Pseudorandom Graphs2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) | 1 Oct 2018 Cross Ref New algorithms for maximum disjoint paths based on tree-likenessMathematical Programming, Vol. 171, No. 1-2 | 14 November 2017 Cross Ref Star chromatic index of subcubic multigraphsJournal of Graph Theory, Vol. 88, No. 4 | 8 December 2017 Cross Ref Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven VerticesCombinatorica, Vol. 38, No. 4 | 31 May 2017 Cross Ref On the chromatic index of join graphs and triangle-free graphs with large maximum degreeDiscrete Applied Mathematics, Vol. 245 | 1 Aug 2018 Cross Ref Node-Based Service-Balanced Scheduling for Provably Guaranteed Throughput and Evacuation Time PerformanceIEEE Transactions on Mobile Computing, Vol. 17, No. 8 | 1 Aug 2018 Cross Ref A theory of linear typings as flows on 3-valent graphsProceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science | 9 July 2018 Cross Ref Chromatic index determined by fractional chromatic indexJournal of Combinatorial Theory, Series B, Vol. 131 | 1 Jul 2018 Cross Ref The Backbone Packet Radio Network coloring for Time Division Multiple Access link scheduling in Wireless Multihop NetworksNetworks, Vol. 71, No. 4 | 30 August 2017 Cross Ref Trees, Paths, Stars, Caterpillars and SpidersAlgorithmica, Vol. 80, No. 6 | 25 October 2016 Cross Ref On colouring (2P2, H) -free and (P5, H) -free graphsInformation Processing Letters, Vol. 134 | 1 Jun 2018 Cross Ref On f-colorings of nearly bipartite graphsInformation Processing Letters, Vol. 134 | 1 Jun 2018 Cross Ref On the algorithmic aspects of strong subcoloringJournal of Combinatorial Optimization, Vol. 35, No. 4 | 6 March 2018 Cross Ref Optimal Joint Routing and Scheduling in Millimeter-Wave Cellular NetworksIEEE INFOCOM 2018 - IEEE Conference on Computer Communications | 1 Apr 2018 Cross Ref Underwater Acoustic Sensor Node Scheduling using an Evolutionary Memetic AlgorithmJournal of Telecommunications and Information Technology, Vol. 1, No. 2018 | 28 March 2018 Cross Ref 3-Colorable Subclasses of P₈-Free GraphsMaria Chudnovsky and Juraj StachoSIAM Journal on Discrete Mathematics, Vol. 32, No. 2 | 15 May 2018AbstractPDF (668 KB) On the structure of (pan, even hole) -free graphsJournal of Graph Theory, Vol. 87, No. 1 | 29 June 2017 Cross Ref On the Relation of Strong Triadic Closure and Cluster DeletionGraph-Theoretic Concepts in Computer Science | 2 September 2018 Cross Ref Reconstructing the History of Syntenies Through Super-ReconciliationComparative Genomics | 8 September 2018 Cross Ref ApproximationsalgorithmenKombinatorische Optimierung | 25 July 2018 Cross Ref A coloring algorithm for 4K1 -free line graphsDiscrete Applied Mathematics, Vol. 234 | 1 Jan 2018 Cross Ref Complexity and Algorithms for a Perfect from Mixed Transactions on and Vol. 15, No. 1 | 1 Jan 2018 Cross Ref Optimization | 14 March 2018 Cross Ref Conjecture Large Maximum of Graph Theory, Vol. No. 4 | 2 March 2017 Cross Ref On the Complexity of Computing of Combinatorics, Vol. No. 4 | 7 August 2017 Cross Ref a Graph Using Mobile Vol. No. 3 | 18 October 2016 Cross Ref The of of graphs with large maximum Mathematics and Computation, Vol. | 1 Nov 2017 Cross Ref graphsJournal of Combinatorial Optimization, Vol. 34, No. 3 | 5 January 2017 Cross Ref On some colorings of graphsDiscrete Applied Mathematics, Vol. | 1 Oct 2017 Cross Ref algorithms in A IEEE 16th International Symposium on Network Computing and Applications | 1 Oct 2017 Cross Ref On the of the of and Combinatorics, Vol. 33, No. 5 | 12 August 2017 Cross Ref scheduling and for on Computing, Vol. 20, No. 3 | 29 November 2016 Cross Ref for paths and of Computer and System Sciences, Vol. | 1 Aug 2017 Cross Ref for the chromatic number of some Programming, Vol. No. 1-2 | 11 November 2016 Cross Ref Subcubic in Steiner triple systemsDiscrete Mathematics, Vol. No. 6 | 1 Jun 2017 Cross Ref and of graphsJournal of Combinatorial Theory, Series B, Vol. | 1 May 2017 Cross Ref A on the Complexity of Coloring Graphs with Forbidden of Graph Theory, Vol. 84, No. 4 | 2 March 2016 Cross Ref An to the via graph coloringDiscrete Mathematics, Vol. No. 4 | 1 Apr 2017 Cross Ref Algorithmic complexity of and the Computer Science, Vol. | 1 Apr 2017 Cross Ref With An Algorithmic Transactions on Networking, Vol. No. 2 | 1 Apr 2017 Cross Ref Graphs with Induced of Graph Theory, Vol. 84, No. 3 | 12 February 2016 Cross Ref Algorithms for and GraphsAlgorithmica, Vol. No. 3 | 4 January 2016 Cross Ref The complexity of for simple Journal of Combinatorics, Vol. | 1 Mar 2017 Cross Ref Euler Partition and Edge and Complexity | 14 April 2017 Cross Ref Minimum and Combinatorial Optimization | 24 May 2017 Cross Ref Approximately Coloring Graphs Without Long Induced Concepts in Computer Science | 2 November 2017 Cross Ref Complexity of coloring graphs without paths and cyclesDiscrete Applied Mathematics, Vol. | 1 Jan 2017 Cross Ref of Applied Mathematics, Vol. | 1 Jan 2017 Cross Ref and of through International Conference on Computing, Networking and Communications | 1 Jan 2017 Cross Ref graph a Letters, Vol. No. 8 | 26 December Cross Ref The complexity of problems on graphs of bounded and Computation, Vol. | 1 Dec 2016 Cross Ref The complexity of counting edge colorings and a for some in the Mathematical Sciences, Vol. No. 1 | 1 September 2016 Cross Ref The scheduling problem with Journal of Research, Vol. No. 3 | 1 Nov 2016 Cross Ref On the algorithmic complexity of Processing Letters, Vol. No. 11 | 1 Nov 2016 Cross Ref Chromatic and maximum Notes in Discrete Mathematics, Vol. | 1 Oct 2016 Cross Ref On a of the of for Mathematics, Vol. No. 9 | 1 Sep 2016 Cross Ref Research Letters, Vol. No. 4 | 1 Jul 2016 Cross Ref On the Complexity of Computing the of a of Graph Theory, Vol. 82, No. 1 | 8 June Cross Ref Optimal and of dense quasirandom graphsJournal of Combinatorial Theory, Series B, Vol. | 1 May 2016 Cross Ref by Edge Coloring for Wireless Sensor IEEE Conference | 1 May 2016 Cross Ref The edge chromatic number of graphsDiscrete Mathematics, Vol. No. 4 | 1 Apr 2016 Cross Ref scheduling for and INFOCOM 2016 - The Annual IEEE International Conference on Computer Communications | 1 Apr 2016 Cross Ref of graphsDiscrete Mathematics, Algorithms and Vol. No. | 26 February 2016 Cross Ref to cover a graphDiscrete Mathematics, Vol. No. 2 | 1 Feb 2016 Cross Ref of Theory | 20 October 2016 Cross Ref of -Free GraphsGraph-Theoretic Concepts in Computer Science | 28 September 2016 Cross Ref Algorithms and Tight for 3 of Small Diameter GraphsAlgorithmica, Vol. No. 1 | 21 October Cross Ref Improved complexity on k Pt -free Journal of Combinatorics, Vol. | 1 Jan 2016 Cross Ref complexity of Computer Science, Vol. | 1 Jan 2016 Cross Ref partition of of bipartite graph Mathematics and Vol. 26, No. 6 | 1 Jan 2016 Cross Ref Vol. 28, No. 1 | 1 Jan 2016 Cross Ref A for in Notes in Discrete Mathematics, Vol. | 1 Dec Cross Ref On the chromatic index of and join Notes in Discrete Mathematics, Vol. | 1 Dec Cross Ref Colorings with and Combinatorics, Vol. No. 6 | 10 January Cross Ref Mathematics, Vol. No. 11 | 1 Nov Cross Ref Optimal and of dense quasirandom Notes in Discrete Mathematics, Vol. | 1 Nov Cross Ref Joint in with and scheduling Vol. 91 | 1 Sep Cross Ref the and problems in of the of Sciences, Vol. No. 3 | 1 Sep Cross Ref On the maximum of by matchings in a cubic graphDiscrete Mathematics, Vol. No. 8 | 1 Aug Cross Ref Edge Colorings of the of and Combinatorics, Vol. No. 4 | 23 March Cross Ref The Chromatic Index of a Graph Maximum Degree and Combinatorics, Vol. No. 4 | 12 April Cross Ref index for networksJournal of Discrete Algorithms, Vol. | 1 Jul Cross Ref of of line graphsDiscrete Applied Mathematics, Vol. | 1 May Cross Ref How are Research Letters, Vol. No. 3 | 1 May Cross Ref coloring and in graphsDiscrete Applied Mathematics, Vol. | 1 Mar Cross Ref scheduling with Annual Conference on Information and Systems | 1 Mar Cross Ref The complexity of the Processing Letters, Vol. No. 2 | 1 Feb Cross Ref of Weighted Algorithms and Computation | 1 Jan Cross Ref Matching in Algorithms | 7 June Cross Ref Scheduling via and Edge and Wireless | 19 June Cross Ref a Perfect from Mixed in | 28 August Cross Ref a Graph Using Mobile and Computation | 27 November Cross Ref List Coloring in the Absence of a Linear Vol. 71, No. 1 | 6 April Cross Ref On of bipartite and Vol. No. 1 | 4 February Cross Ref The of for International Conference on with Applications in and | 1 Dec Cross Ref in Radio NetworksIEEE Transactions on Mobile Computing, Vol. No. 11 | 1 Nov Cross