Total coloring and total matching: polyhedra and facets

DOI10.1016/j.ejor.2022.02.025OpenAlexW4213181986MaRDI QIDQ2673562

Luca Ferrarini, Stefano Gualandi

Publication date: 10 June 2022

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2105.09827

zbMATH Keywords

integer programmingcombinatorial optimizationtotal coloringtotal matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Total colorings-a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the equitable total chromatic number of cubic graphs
• Edge coloring: a natural model for sports scheduling
• An exact approach for the vertex coloring problem
• A branch and cut solver for the maximum stable set problem
• A comparison of two edge-coloring formulations
• A simple branching scheme for vertex coloring problems
• Determining the total colouring number is NP-hard
• The stable set polytope of quasi-line graphs
• A memetic algorithm for graph coloring
• A polyhedral approach to edge coloring
• A class of facet producing graphs for vertex packing polyhedra
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• Antiweb-wheel inequalities and their separation problems over the stable set polytopes
• Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation
• Total colourings of graphs
• Maximum-weight stable sets and safe lower bounds for graph coloring
• Total coloring conjecture for certain classes of graphs
• New integer linear programming models for the vertex coloring problem
• A new branch-and-bound algorithm for the maximum edge-weighted clique problem
• Symmetric ILP: Coloring and small integers
• A branch-and-cut algorithm for graph coloring
• On some applications of the selective graph coloring problem
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
• A survey on vertex coloring problems
• Approximate graph coloring by semidefinite programming
• On the Computational Complexity of Combinatorial Problems
• Total matchings and total coverings of graphs
• A Column Generation Approach for Graph Coloring
• Graph Coloring Lower Bounds from Decision Diagrams
• Constraint and Satisfiability Reasoning for Graph Coloring
• On the facial structure of set packing polyhedra
• A new mixed integer linear programming formulation for the maximum degree bounded connected subgraph problem
• Selected Topics in Column Generation
• Maximum matching and a polyhedron with 0,1-vertices
• Total Graphs and Traversability
• A Short Proof of the Factor Theorem for Finite Graphs
• Constraint programming-based column generation
• A branch-and-cut algorithm for the maximum cardinality stable set problem

This page was built for publication: Total coloring and total matching: polyhedra and facets