Graph imperfection. II

DOI10.1006/jctb.2001.2043zbMath1018.05027OpenAlexW1984779409MaRDI QIDQ1850632

Stefanie Gerke, Colin J. H. McDiarmid

Publication date: 11 December 2002

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

Full work available at URL: https://semanticscholar.org/paper/e066ad216893ed60b763d4da7c7288a7ee2db6d0

zbMATH Keywords

random graphsimperfection ratiocochromatic numberradio channel assignment

Mathematics Subject Classification ID

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

Related Items

A Sum of Squares Characterization of Perfect Graphs, Disproving the normal graph conjecture, Characterizing and bounding the imperfection ratio for some classes of graphs, Perfectness and imperfectness of unit disk graphs on triangular lattice points, Graph imperfection. I, Graph imperfection. II

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the independence number of random graphs
• On a packing and covering problem
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• On the independence and chromatic numbers of random regular graphs
• Geometric algorithms and combinatorial optimization
• Explicit Ramsey graphs and orthonormal labelings
• Graph imperfection. II
• Normal hypergraphs and the perfect graph conjecture
• The Independence Ratio of Regular Graphs
• On the hardness of approximating minimization problems
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The chromatic number of random graphs
• The chromatic number of random graphs
• 25 pretty graph colouring problems
• On the chromatic number of random graphs