Publication

Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs

2004
Reports

Abstract

It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even no conjecture at hand today. Such a conjecture exists for the class of quasi-line graphs. This class of graphs is a proper superclass of line graphs and a proper subclass of claw-free graphs for which it is known that not all facets have 0/1 normal vectors. Ben Rebea's conjecture states that the stable set polytope of a quasi-line graph is completely described by clique-family inequalities. Chudnovsky and Seymour recently provided a decomposition result for claw-free graphs and proved that Ben Rebea's conjecture holds, if the quasi-line graph is not a fuzzy circular interval graph. In this paper, we give a proof of Ben Rebea's conjecture by showing that it also holds for fuzzy circular interval graphs. Our result builds upon an algorithm of Bartholdi, Orlin and Ratliff which is concerned with integer programs defined by circular ones matrices.

Official source

https://infoscience.epfl.ch/entities/publication/0fcb06af-597c-4854-87cc-1c065300dd3e

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2004
Reports

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/0fcb06af-597c-4854-87cc-1c065300dd3e

About this result

Related concepts (32)

Claw-free graph

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph comprising three edges, three leaves, and a central vertex). A claw-free graph is a graph in which no induced subgraph is a claw; i.e., any subset of four vertices has other than only three edges connecting them in this pattern. Equivalently, a claw-free graph is a graph in which the neighborhood of any vertex is the complement of a triangle-free graph.

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.

Graph isomorphism

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if and are adjacent in H. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection. If an isomorphism exists between two graphs, then the graphs are called isomorphic and denoted as . In the case when the bijection is a mapping of a graph onto itself, i.

Related publications (11)

Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs

Chat with Graph Search

Tight bounds for intersection‐reverse sequences, edge‐ordered graphs, and applications

A Benders decomposition for maximum simulated likelihood estimation of advanced discrete choice models

Scaling a Reliable Distributed System