The NP-Completeness of Edge-Coloring
From MaRDI portal
Publication:3928241
DOI10.1137/0210055zbMath0473.68034OpenAlexW2102669784WikidataQ29013951 ScholiaQ29013951MaRDI QIDQ3928241
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/37c92599655b9f66850f1e4e0e48ad045abad8f6
Related Items
The chromatic index of nearly bipartite multigraphs ⋮ Intersection graphs of paths in a tree ⋮ A note on optical routing on trees ⋮ Coloring problems on bipartite graphs of small diameter ⋮ Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four ⋮ Improving a family of approximation algorithms to edge color multigraphs ⋮ Improved edge-coloring with three colors ⋮ On a limit of the method of Tashkinov trees for edge-colouring ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ A self-stabilizing \((\Delta +4)\)-edge-coloring algorithm for planar graphs in anonymous uniform systems ⋮ Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time ⋮ Edge-colouring of joins of regular graphs. I ⋮ The tournament scheduling problem with absences ⋮ The strong chromatic number of partial triple systems ⋮ A faster test for 4-flow-criticality in snarks ⋮ On the chromatic index of cographs and join graphs ⋮ Edge covering coloring of nearly bipartite graphs ⋮ The parameterised complexity of list problems on graphs of bounded treewidth ⋮ Complexity of coloring graphs without paths and cycles ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ Excessive factorizations of bipartite multigraphs ⋮ Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface ⋮ Computing clique and chromatic number of circular-perfect graphs in polynomial time ⋮ On the complexity of adjacent resource scheduling ⋮ Time slot scheduling of compatible jobs ⋮ Edge-colouring and total-colouring chordless graphs ⋮ Algorithmic complexity of proper labeling problems ⋮ On excessive index of certain networks ⋮ Parameterized complexity of max-lifetime target coverage in wireless sensor networks ⋮ On the max-weight edge coloring problem ⋮ Edge-chromatic numbers of Mycielski graphs ⋮ Injective colorings with arithmetic constraints ⋮ Computational complexity of covering three-vertex multigraphs ⋮ Three ways to cover a graph ⋮ Approximating the chromatic index of multigraphs ⋮ Minimum decomposition into convex binary matrices ⋮ The edge chromatic number of outer-1-planar graphs ⋮ Optimally edge-colouring outerplanar graphs is in NC ⋮ Determining the total colouring number is NP-hard ⋮ The chromatic index of multigraphs that are nearly full ⋮ Local algorithms for edge colorings in UDGs ⋮ Some criteria for a graph to be class 1 ⋮ Total chromatic number of unichord-free graphs ⋮ Relating edge-coverings to the classification of \(\mathbb Z^k_2\)-magic graphs ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ Randomly colouring graphs (a combinatorial view) ⋮ The 2nd-order conditional 3-coloring of claw-free graphs ⋮ On upper bounds for parameters related to the construction of special maximum matchings ⋮ The complexity of the zero-sum 3-flows ⋮ Measures of edge-uncolorability of cubic graphs ⋮ Excessive index for mesh derived networks ⋮ On the equivalence covering number of splitgraphs ⋮ Improved complexity results on \(k\)-coloring \(P_t\)-free graphs ⋮ Successive partition of edges of bipartite graph into matchings ⋮ An introduction to the discharging method via graph coloring ⋮ On complexity of special maximum matchings constructing ⋮ Critical hereditary graph classes: a survey ⋮ Stable sets versus independent sets ⋮ Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs ⋮ A comparison of two edge-coloring formulations ⋮ \([r,s,t\)-coloring of trees and bipartite graphs] ⋮ Algorithmic complexity of weakly semiregular partitioning and the representation number ⋮ Approximating the maximum 2- and 3-edge-colorable subgraph problems ⋮ Interval edge-colorings of complete graphs and \(n\)-dimensional cubes ⋮ On disjoint matchings in cubic graphs ⋮ Compact scheduling of zero-one time operations in multi-stage systems ⋮ Complexity of approximation of 3-edge-coloring of graphs ⋮ On multiples of simple graphs and Vizing's theorem ⋮ Approximating the max-edge-coloring problem ⋮ Decompositions for edge-coloring join graphs and cobipartite graphs ⋮ Two easy duality theorems for product partial orders ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Edge-coloring of 3-uniform hypergraphs ⋮ The complexity of list edge-partitions for simple graphs ⋮ Approximation algorithm for maximum edge coloring ⋮ Local edge colouring of Yao-like subgraphs of unit disk graphs ⋮ The chromatic index of a graph whose core is a cycle of order at most 13 ⋮ Characterization of a class of graphs related to pairs of disjoint matchings ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs ⋮ The chromatic index of graphs with large maximum degree, where the number of vertices of maximum degree is relatively small ⋮ Achieving maximum chromatic index in multigraphs ⋮ On star and caterpillar arboricity ⋮ On linear k-arboricity ⋮ Some results on graphs without long induced paths ⋮ Colouring vertices of triangle-free graphs without forests ⋮ Graph coloring with cardinality constraints on the neighborhoods ⋮ Connected greedy coloring of \(H\)-free graphs ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture ⋮ Mixed graph edge coloring ⋮ Approximating the maximum 3-edge-colorable subgraph problem ⋮ On Vizing's bound for the chromatic index of a multigraph ⋮ Completing partial commutative quasigroups constructed from partial Steiner triple systems is NP-complete ⋮ An application of Tutte's theorem to 1-factorization of regular graphs of high degree ⋮ The chromatic index of graphs with large maximum degree ⋮ Embedding partial Steiner triple systems is NP-complete ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Decomposition by clique separators ⋮ Some sufficient conditions for a graph to be of \(C_f\) 1 ⋮ Algorithms and almost tight results for 3-colorability of small diameter graphs ⋮ \((p,k)\)-coloring problems in line graphs ⋮ Superposition and constructions of graphs without nowhere-zero \(k\)-flows ⋮ Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion ⋮ On claw-free asteroidal triple-free graphs ⋮ How to find overfull subgraphs in graphs with large maximum degree ⋮ The hardness of approximation: Gap location ⋮ List-edge-colouring planar graphs with precoloured edges ⋮ Regular codes in regular graphs are difficult ⋮ Algorithmic problems in right-angled Artin groups: complexity and applications ⋮ Space-efficient Euler partition and bipartite edge coloring ⋮ The probabilistic method yields deterministic parallel algorithms ⋮ Trees, paths, stars, caterpillars and spiders ⋮ The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3 ⋮ Triangulations of 3-way regular tripartite graphs of degree 4, with applications to orthogonal latin squares ⋮ Parallel O(log n) time edge-colouring of trees and Halin graphs ⋮ The complexity of scheduling independent two-processor tasks on dedicated processors ⋮ Preassignment requirements in chromatic scheduling ⋮ Vertex-splitting and chromatic index critical graphs ⋮ Edge-colouring random graphs ⋮ Edge-packings of graphs and network reliability ⋮ Class one graphs ⋮ Matching structure and the matching lattice ⋮ On edge perfectness and classes of bipartite graphs ⋮ Tight approximations for resource constrained scheduling and bin packing ⋮ Coloring edges of self-complementary graphs ⋮ A linear time algorithm for edge coloring of binomial trees ⋮ Applications of edge coloring of multigraphs to vertex coloring of graphs ⋮ Minimum multiplicity edge coloring via orientation ⋮ Two conjectures on edge-colouring ⋮ Gallai graphs and anti-Gallai graphs ⋮ Characterizing and edge-colouring split-indifference graphs ⋮ The maximum chromatic index of multigraphs with given \(\Delta \) and \(\mu \) ⋮ Small edge sets meeting all triangles of a graph ⋮ When patrolmen become corrupted: monitoring a graph using faulty mobile robots ⋮ Covering regular graphs ⋮ Disconnected \(g_c\)-critical graphs ⋮ On the complexity of computing MP distance between binary phylogenetic trees ⋮ On edge-colouring indifference graphs ⋮ On the \(b\)-continuity of the lexicographic product of graphs ⋮ Edge ranking of graphs is hard ⋮ A coloring algorithm for \(4 K_1\)-free line graphs ⋮ 3-colouring AT-free graphs in polynomial time ⋮ Decompositions for the edge colouring of reduced indifference graphs. ⋮ Shifted matroid optimization ⋮ The complexity of the \(T\)-coloring problem for graphs with small degree ⋮ On edge covering colorings of graphs ⋮ New bounds for optimum traffic assignment in satellite communication. ⋮ Edge-colouring of joins of regular graphs. II ⋮ Polyhedron of triangle-free simple 2-matchings in subcubic graphs ⋮ On the Grundy and \(b\)-chromatic numbers of a graph ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ On \(f\)-colorings of nearly bipartite graphs ⋮ Graphs whose edge set can be partitioned into maximum matchings ⋮ On the choice number of claw-free perfect graphs ⋮ The ellipsoid method and its consequences in combinatorial optimization ⋮ Graphs with small fall-spectrum ⋮ 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs. ⋮ An appraisal of computational complexity for operations researchers ⋮ Generalization of a theorem of Kotzig and a prescribed coloring of the edges of planar graphs ⋮ The complexity of controlled selection ⋮ NP-completeness of edge-colouring some restricted graphs ⋮ A polyhedral approach to edge coloring ⋮ Graph edge coloring: a survey ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Some results concerning the complexity of restricted colorings of graphs ⋮ Edge colouring line graphs of unicyclic graphs ⋮ Classifying \(k\)-edge colouring for \(H\)-free graphs ⋮ The classification of \(f\)-coloring of graphs with large maximum degree ⋮ The multi-league sports scheduling problem, or how to schedule thousands of matches ⋮ Chromatic index determined by fractional chromatic index ⋮ Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs ⋮ On the chromatic index of join graphs and triangle-free graphs with large maximum degree ⋮ On the algorithmic aspects of strong subcoloring ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ \(b\)-coloring of tight graphs ⋮ An upper bound for the choice number of star edge coloring of graphs ⋮ Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation ⋮ Designing optimally multiplexed SNP genotyping assays ⋮ Parameterized complexity of \textsc{maximum edge colorable subgraph} ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ How important are branching decisions: fooling MIP solvers ⋮ Three-coloring and list three-coloring of graphs without induced paths on seven vertices ⋮ Complexity and algorithms for injective edge-coloring in graphs ⋮ On sum coloring of graphs ⋮ Efficient algorithms for path partitions ⋮ Jump number maximization for proper interval graphs and series-parallel graphs ⋮ Near-optimal, distributed edge colouring via the nibble method ⋮ The smallest pair of cospectral cubic graphs with different chromatic indexes ⋮ Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors ⋮ Short solution of Kotzig's problem for bipartite graphs ⋮ Linear \(k\)-arboricities on trees ⋮ Parameterized complexity of maximum edge colorable subgraph ⋮ On coloring a class of claw-free and hole-twin-free graphs ⋮ Revising Johnson's table for the 21st century ⋮ Decompositions to degree-constrained subgraphs are simply reducible to edge-colorings ⋮ Edge coloring nearly bipartite graphs ⋮ Interval edge coloring of a graph with forbidden colors ⋮ Total colouring regular bipartite graphs is NP-hard ⋮ Edge dominating set and colorings on graphs with fixed clique-width ⋮ 4-edge-coloring graphs of maximum degree 3 in linear time ⋮ Routing and path multicoloring ⋮ Colouring simplicial complexes via the Lechuga-Murillo's model ⋮ Integer round-up property for the chromatic number of some \(h\)-perfect graphs ⋮ On the Nash number and the diminishing Grundy number of a graph ⋮ The chromatic index of proper circular-arc graphs of odd maximum degree which are chordal ⋮ On coloring a class of claw-free graphs. ⋮ Edge-colouring of join graphs ⋮ Characterization of saturated graphs related to pairs of disjoint matchings ⋮ On the algorithmic complexity of zero-sum edge-coloring ⋮ An improvement to the Hilton-Zhao vertex-splitting conjecture ⋮ Weighted 2-sections and hypergraph reconstruction ⋮ Switching 3-edge-colorings of cubic graphs ⋮ Subcubic planar graphs of girth 7 are class I ⋮ Perfect matching covering, the Berge-Fulkerson conjecture, and the Fan-Raspaud conjecture ⋮ Colouring series-parallel graphs ⋮ The complexity of \(L(p, q)\)-edge-labelling ⋮ More on the rainbow disconnection in graphs ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ Narrow sieves for parameterized paths and packings ⋮ On some domination colorings of graphs ⋮ Subcubic trades in Steiner triple systems ⋮ Determining the circular flow number of a cubic graph ⋮ On generalisations of the AVD conjecture to digraphs ⋮ Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ Chromatic index of dense quasirandom graphs ⋮ Regular pattern-free coloring ⋮ Co-density and fractional edge cover packing ⋮ On the complexity of cd-coloring of graphs ⋮ Colouring \((P_r + P_s)\)-free graphs ⋮ Certifying coloring algorithms for graphs without long induced paths ⋮ Disjoint stable matchings in linear time ⋮ Bears with hats and independence polynomials ⋮ Vizing's 2-factor conjecture involving toughness and maximum degree conditions ⋮ Approximate separable multichoice optimization over monotone systems ⋮ Overfullness of critical class 2 graphs with a small core degree ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Edge-colouring graphs with bounded local degree sums ⋮ A \(\frac{5}{2}\)-approximation algorithm for coloring rooted subtrees of a degree 3 tree ⋮ \(b\)-continuity and partial Grundy coloring of graphs with large girth ⋮ Using the minimum maximum flow degree to approximate the flow coloring problem ⋮ Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees ⋮ On Vizing's edge colouring question ⋮ Restricted extension of sparse partial edge colorings of hypercubes ⋮ Grundy coloring in some subclasses of bipartite graphs and their complements ⋮ Allocating indivisible items with minimum dissatisfaction on preference graphs ⋮ 3-colouring \(P_t\)-free graphs without short odd cycles ⋮ A Markov chain on the solution space of edge colorings of bipartite graphs ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ New Steiner 2-designs from old ones by paramodifications ⋮ On 2-factors with a bounded number of odd components ⋮ On balanced colorings of sparse hypergraphs ⋮ Coloring graphs without short cycles and long induced paths ⋮ The complexity of LSH feasibility ⋮ Edge-coloring almost bipartite multigraphs ⋮ The complexity of the proper orientation number ⋮ Better 3-coloring algorithms: excluding a triangle and a seven vertex path ⋮ New bounds and constraint propagation techniques for the clique partitioning problem ⋮ Bounded max-colorings of graphs ⋮ The hunting of a snark with total chromatic number 5 ⋮ On the average degree of edge chromatic critical graphs ⋮ Chromatic Gallai identities operating on Lovász number ⋮ \(f\)-class two graphs whose \(f\)-cores have maximum degree two ⋮ Superposition of snarks revisited ⋮ Algorithms for finding distance-edge-colorings of graphs ⋮ Packing \([1, \Delta \)-factors in graphs of small degree] ⋮ The complexity of counting edge colorings for simple graphs ⋮ An upper bound for the chromatic number of line graphs ⋮ Coloring temporal graphs ⋮ Edge-colouring of regular graphs of large degree ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Decomposition of university course timetabling. A systematic study of subproblems and their complexities ⋮ Some graphs of class 1 for \(f\)-colorings ⋮ The \(k\)-edge intersection graphs of paths in a tree ⋮ Polynomial time complexity of edge colouring graphs with bounded colour classes ⋮ Mutual exclusion scheduling with interval graphs or related classes. II ⋮ Coloring vertices of claw-free graphs in three colors ⋮ On the computational complexity of partial covers of theta graphs ⋮ List coloring in the absence of a linear forest ⋮ Small snarks with large oddness ⋮ Chromatic index of graphs with no cycle with a unique chord ⋮ Irreducible snarks of given order and cyclic connectivity ⋮ The satisfactory partition problem ⋮ On the fg-coloring of graphs ⋮ Projective, affine, and abelian colorings of cubic graphs ⋮ Goldberg's conjecture is true for random multigraphs ⋮ On strong proper connection number of cubic graphs ⋮ \(H\)-colouring \(P_t\)-free graphs in subexponential time ⋮ Colouring square-free graphs without long induced paths ⋮ Edge-coloring of multigraphs ⋮ Vizing's and Shannon's theorems for defective edge colouring ⋮ On the algorithmic complexity of determining the AVD and NSD chromatic indices of graphs ⋮ From edge-coloring to strong edge-coloring ⋮ Domination, coloring and stability in \(P_5\)-reducible graphs ⋮ On the maximum fraction of edges covered by \(t\) perfect matchings in a cubic bridgeless graph ⋮ Morphology of small snarks ⋮ Excessive \([l, m\)-factorizations] ⋮ Bounds for the rainbow disconnection numbers of graphs ⋮ The chromatic index of a claw-free graph whose core has maximum degree 2 ⋮ Edge colorings of the direct product of two graphs ⋮ On interval \(\Delta\)-coloring of bipartite graphs ⋮ Minimizing total completion time in multiprocessor job systems with energy constraint ⋮ The number of disjoint perfect matchings in semi-regular graphs ⋮ Disjointness graphs of segments in the space ⋮ Space-Efficient Euler Partition and Bipartite Edge Coloring ⋮ Proof of the 1-factorization and Hamilton Decomposition Conjectures ⋮ Finding a Perfect Phylogeny from Mixed Tumor Samples ⋮ Efficient Vertex- and Edge-Coloring of Outerplanar Graphs ⋮ Determining the thickness of graphs is NP-hard ⋮ Tight products and graph expansion ⋮ 4-Coloring H-Free Graphs When H Is Small ⋮ THE PROPORTIONAL COLORING PROBLEM: OPTIMIZING BUFFERS IN RADIO MESH NETWORKS ⋮ A parallel algorithm for edge-coloring partial k-trees ⋮ Unnamed Item ⋮ Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs ⋮ On Cubic Bridgeless Graphs Whose Edge-Set Cannot be Covered by Four Perfect Matchings ⋮ On $g_c$-colorings of nearly bipartite graphs ⋮ The Fan–Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks ⋮ Properties of Large 2-Crossing-Critical Graphs ⋮ Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem ⋮ Colouring square-free graphs without long induced paths. ⋮ Solving Matching Problems Efficiently in Bipartite Graphs ⋮ Optimal Online Edge Coloring of Planar Graphs with Advice ⋮ Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph ⋮ Approximation of 3-Edge-Coloring of Cubic Graphs ⋮ Asymptotics of the chromatic number for quasi-line graphs ⋮ Edge Coloring of Split Graphs ⋮ Sufficient conditions for a graph to be edge-colorable with maximum degree colors ⋮ The Proportional Colouring Problem: Optimizing Buffers in Wireless Mesh Networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the structure of (pan, even hole)‐free graphs ⋮ 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ A survey of graph coloring - its types, methods and applications ⋮ Optimal path and cycle decompositions of dense quasirandom graphs ⋮ Improved bounds for the chromatic index of graphs and multigraphs ⋮ Densities, Matchings, and Fractional Edge-Colorings ⋮ Excluding Minors in Cubic Graphs ⋮ Chromatic index, treewidth and maximum degree ⋮ COLORING ALGORITHMS ON SUBCUBIC GRAPHS ⋮ Facial rainbow edge-coloring of simple 3-connected plane graphs ⋮ ON 4-EDGE COLORING OF CUBIC GRAPHS CONTAINING “SMALL” NON-PLANAR SUBGRAPHS ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ 3-Colorable Subclasses of $P_8$-Free Graphs ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ Bicolored matchings in some classes of graphs ⋮ Bicolored matchings in some classes of graphs ⋮ Chromatic index, treewidth and maximum degree ⋮ The regular number of a graph ⋮ On the use of graphs in discrete tomography ⋮ On the use of graphs in discrete tomography ⋮ Star Chromatic Index ⋮ Very fast parallel algorithms for approximate edge coloring ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The complexity of arc-colorings for directed hypergraphs ⋮ Clique-perfectness of complements of line graphs ⋮ On the relation of strong triadic closure and cluster deletion ⋮ Vizing's coloring algorithm and the fan number ⋮ On the Maximum Edge Coloring Problem ⋮ Approximately coloring graphs without long induced paths ⋮ Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ 3-Regular Non 3-Edge-Colorable Graphs with Polyhedral Embeddings in Orientable Surfaces ⋮ Generalized edge-colorings of weighted graphs ⋮ The complexity of arc-colorings for directed hypergraphs ⋮ On the fractionalf-chromatic index of a graph ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Unnamed Item ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ On the Complexity of Computing the Excessive [B-Index of a Graph] ⋮ Optimal edge-coloring with edge rate constraints ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ S_12 and P_12-colorings of cubic graphs ⋮ Clique-perfectness of complements of line graphs ⋮ Coloring Graphs without Short Cycles and Long Induced Paths ⋮ Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians ⋮ The chromatic index of strongly regular graphs ⋮ Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 ⋮ Colouring (P_r+P_s)-Free Graphs ⋮ Colouring H-free graphs of bounded diameter. ⋮ The Hilton--Zhao Conjecture is True for Graphs with Maximum Degree 4 ⋮ On edge-colouring indifference graphs ⋮ Unnamed Item ⋮ List Coloring in the Absence of a Linear Forest ⋮ On Coloring Problems of Snark Families ⋮ On characterizing Vizing's edge colouring bound ⋮ Induced Embeddings into Hamming Graphs. ⋮ Unnamed Item ⋮ Fractionally Edge Colouring Graphs with Large Maximum Degree in Linear Time ⋮ A Combinatorial Algorithm to Optimally Colour the Edges of the Graphs That Are Join of Regular Graphs ⋮ Circuit Double Covers of Graphs ⋮ A brief history of edge-colorings – with personal reminiscences ⋮ Injective edge coloring of graphs ⋮ On some arboricities in planar graphs ⋮ Randomized Δ-edge colouring via exchanges of complex colours ⋮ Edge-Colourings of Cubic Graphs and Universal Steiner Triple Systems ⋮ The Overfullness of Graphs with Small Minimum Degree and Large Maximum Degree ⋮ A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ On the maximum number of edges in planar graphs of bounded degree and matching number ⋮ Acyclic chromatic index of chordless graphs ⋮ The overfull conjecture on split-comparability and split-interval graphs ⋮ Independence number of edge‐chromatic critical graphs ⋮ Simple reduction of f-colorings to edge-colorings ⋮ Structure in approximation classes ⋮ Graph and hypergraph colouring via nibble methods: a survey ⋮ Edge coloring graphs with large minimum degree ⋮ Orientation‐based edge‐colorings and linear arboricity of multigraphs ⋮ Perfect matching in bipartite hypergraphs subject to a demand graph ⋮ Near-optimal distributed edge coloring ⋮ More results on the \(z\)-chromatic number of graphs ⋮ An alternating direction method of multipliers for solving user equilibrium problem ⋮ On the chromatic edge stability index of graphs ⋮ Pairs of disjoint matchings and related classes of graphs ⋮ Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs ⋮ Acyclic coloring of products of digraphs ⋮ Further split graphs known to be class 1 and a characterization of subgraph-overfull split graphs ⋮ Deciding whether four perfect matchings can cover the edges of a snark is NP-complete ⋮ On Gupta’s Codensity Conjecture ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs ⋮ On the price of independence for vertex cover, feedback vertex set and odd cycle transversal ⋮ Complexity of graph covering problems ⋮ On determining when small embeddings of partial Steiner triple systems exist ⋮ The core conjecture of Hilton and Zhao ⋮ Overfullness of edge‐critical graphs with small minimal core degree ⋮ Diverse collections in matroids and graphs ⋮ How many matchings cover the nodes of a graph? ⋮ Online Edge Coloring via Tree Recurrences and Correlation Decay ⋮ Unnamed Item ⋮ Diverse Pairs of Matchings ⋮ The complexity of path coloring and call scheduling ⋮ The complexity of \(L(p, q)\)-edge-labelling ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ On the maximum number of edges in chordal graphs of bounded degree and matching number
