Colouring Non-sparse Random Intersection Graphs

DOI10.1007/978-3-642-03816-7_51zbMath1250.05097OpenAlexW1608061481MaRDI QIDQ3182958

Christoforos L. Raptopoulos, Sotiris E. Nikoletseas, Paul G. Spirakis

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_51

zbMATH Keywords

intersection graphselection probabilitycolouring hypergraphs\textsf{CliqueColour}finding a proper colouringlabel sets of verticesrandon intersection graph (RIG)

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Random subcube intersection graphs. I: Cliques and covering ⋮ On Some Combinatorial Properties of Random Intersection Graphs ⋮ On the chromatic number of non-sparse random intersection graphs ⋮ The chromatic number of random intersection graphs ⋮ On the Chromatic Index of Random Uniform Hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the independence number and Hamiltonicity of uniform random intersection graphs
• On the independence number of random graphs
• Large independent sets in general random intersection graphs
• The distant-2 chromatic number of random proximity and random geometric graphs
• On the chromatic number of simple triangle-free triple systems
• Contention-free MAC protocols for asynchronous wireless sensor networks
• A spectral technique for coloring random 3-colorable graphs (preliminary version)
• Secure communication over radio channels
• RANDOM INTERSECTION GRAPHS WITH TUNABLE DEGREE DISTRIBUTION AND CLUSTERING
• An algorithmic approach to the Lovász local lemma. I
• On Random Intersection Graphs: The Subgraph Problem
• The vertex degree distribution of random intersection graphs
• Random intersection graphs whenm=?(n): An equivalence theorem relating the evolution of theG(n,m,p) andG(n,p) models
• Coloring Random Intersection Graphs and Complex Networks
• A Guided Tour in Random Intersection Graphs
• Secret Swarm Unit Reactive k −Secret Sharing
• Automata, Languages and Programming
• Automata, Languages and Programming
• Algorithms and Computation
• The chromatic number of random graphs
• The chromatic number of random graphs
• On a combinatorial game
• Graph colouring and the probabilistic method

This page was built for publication: Colouring Non-sparse Random Intersection Graphs