Graph imperfection. I

DOI10.1006/JCTB.2001.2042zbMATH Open1027.05043OpenAlexW2913391020MaRDI QIDQ1850556FDOQ1850556

Authors: Stefanie Gerke, Colin 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

Recommendations

• Graph imperfection. II
• Colouring proximity graphs in the plane
• Graph imperfection and channel assignment
• Graph Imperfection with a Co-Site Constraint
• Weighted Improper Colouring

zbMATH Keywords

perfect graphsstable set polytopeimperfection ratioweighted colouringradio channel assignment

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (23)

• Disproving the normal graph conjecture
• Title not available (Why is that?)
• Graph imperfection and channel assignment
• The performance of an upper bound on the fractional chromatic number of weighted graphs
• The nonidealness index of rank-ideal matrices
• Characterizing and bounding the imperfection ratio for some classes of graphs
• Distributed coloring and the local structure of unit-disk graphs
• Clutter nonidealness
• A polyhedral approach to the stability of a family of coalitions
• On a certain class of nonideal clutters
• Graph Imperfection with a Co-Site Constraint
• Distributed coloring and the local structure of unit-disk graphs
• Graph imperfection. II
• Comparing imperfection ratio and imperfection index for graph classes
• Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
• Perfectness and imperfectness of unit disk graphs on triangular lattice points
• Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model
• Constructions for normal graphs and some consequences
• The nonidealness index of circulant matrices
• On determining the imperfection ratio
• A comparison between lift-and-project indices and imperfection ratio on web graphs
• Probabilistic refinement of the asymptotic spectrum of graphs
• Flipping triangles and rectangles

This page was built for publication: Graph imperfection. I

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850556)