Decomposing complete edge-chromatic graphs and hypergraphs. Revisited

DOI10.1016/j.dam.2009.06.026zbMath1209.05081OpenAlexW1967454590MaRDI QIDQ967361

Vladimir A. Gurvich

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.06.026

zbMATH Keywords

graphshypergraphsmodular decompositionpositional gamessubstitutionread-once functionsGallai graphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (16)

A characterization of claw-free CIS graphs and new results on the order of CIS graphs ⋮ On equistable, split, CIS, and related classes of graphs ⋮ Reconstructing unrooted phylogenetic trees from symbolic ternary metrics ⋮ Friendship two-graphs ⋮ Total tightness implies Nash-solvability for three-person game forms ⋮ Computing lexicographically safe Nash equilibria in finite two-person games with tight game forms given by oracles ⋮ On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems ⋮ Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs ⋮ Nash-solvable two-person symmetric cycle game forms ⋮ All partitions have small parts -- Gallai-Ramsey numbers of bipartite graphs ⋮ Gallai colorings and domination in multipartite digraphs ⋮ Not complementary connected and not CIS \(d\)-graphs form weakly monotone families ⋮ Connected colourings of complete graphs and hypergraphs ⋮ Sandwich problem for \(\varPi\)- and \(\varDelta\)-free multigraphs and its applications to positional games ⋮ Three-way symbolic tree-maps and ultrametrics ⋮ Vertex- and edge-minimal and locally minimal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Proof of Chvátal's conjecture on maximal stable sets and maximal cliques in graphs
• Combinatorial characterization of read-once formulae
• Edge-colored complete graphs with precisely colored subgraphs
• Colored graphs without colorful cycles
• Not complementary connected and not CIS \(d\)-graphs form weakly monotone families
• Vertex- and edge-minimal and locally minimal graphs
• Minimal and locally minimal games and game forms
• A note on perfect graphs
• On the X-join decomposition for undirected graphs
• Cores of effectivity functions and implementation theory
• Perfect couples of graphs
• Modular decomposition and transitive orientation
• Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
• Effectivity functions, game forms, games, and rights
• Graphs indecomposable with respect to the X-join
• Generating Boolean \(\mu\)-expressions
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• On effectivity functions of game forms
• On graphs whose maximal cliques and stable sets intersect
• A characterization of perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• On a property of the class of n-colorable graphs
• A Characterization of Almost CIS Graphs
• A Fast Algorithm for the Decomposition of Graphs and Posets
• Incremental modular decomposition
• The solvability of positional games in pure strategies
• Graph Classes: A Survey
• Lambda composition
• Edge colorings of complete graphs without tricolored triangles
• Dual subimplicants of positive Boolean functions
• Transitiv orientierbare Graphen
• Bottleneck extrema
• Graph pairs and their entropies: Modularity problems

This page was built for publication: Decomposing complete edge-chromatic graphs and hypergraphs. Revisited