Graph imperfection. I

DOI10.1006/jctb.2001.2042zbMath1027.05043OpenAlexW2913391020MaRDI QIDQ1850556

Stefanie Gerke, Colin J. H. McDiarmid

Publication date: 10 December 2002

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jctb.2001.2042

zbMATH Keywords

stable set polytopeperfect graphsimperfection ratioweighted colouringradio channel assignment

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Related Items (20)

Comparing Imperfection Ratio and Imperfection Index for Graph Classes ⋮ Flipping triangles and rectangles ⋮ The nonidealness index of circulant matrices ⋮ Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model ⋮ Approximate strong separation with application in fractional graph coloring and preemptive scheduling. ⋮ Disproving the normal graph conjecture ⋮ A polyhedral approach to the stability of a family of coalitions ⋮ The performance of an upper bound on the fractional chromatic number of weighted graphs ⋮ Unnamed Item ⋮ Clutter nonidealness ⋮ On a certain class of nonideal clutters ⋮ The nonidealness index of rank-ideal matrices ⋮ Constructions for normal graphs and some consequences ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Characterizing and bounding the imperfection ratio for some classes of graphs ⋮ Probabilistic refinement of the asymptotic spectrum of graphs ⋮ Unnamed Item ⋮ Perfectness and imperfectness of unit disk graphs on triangular lattice points ⋮ On determining the imperfection ratio

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polytope des independants d'un graphe série-parallèle
• Unit disk graphs
• Geometric algorithms and combinatorial optimization
• Improving heuristics for the frequency assignment problem
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• Corrigendum: Static frequency assignment in cellular networks
• Choosability and fractional chromatic numbers
• On coloring unit disk graphs
• On certain polytopes associated with graphs
• Graph imperfection. II
• A characterization of perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• On the width—length inequality
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Line perfect graphs
• Channel assignment and weighted coloring
• The fractional chromatic number of mycielski's graphs
• (2 + ?)-Coloring of planar graphs with large odd-girth
• The Strong Perfect Graph Conjecture for Planar Graphs
• Sur le coloriage des graphs
• 25 pretty graph colouring problems
• Channel assignment and multicolouring of the induced subgraphs of the triangular lattice

This page was built for publication: Graph imperfection. I